Leetcode 3

https://leetcode.com/problems/longest-substring-without-repeating-characters/

문제:

내 솔루션:

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
    
        substring = ""
        maxcount = 0
        
        for char in s:
            if char not in substring:
                substring += char
                
            else: 
                maxcount = max(len(substring), maxcount)
                idx = substring.index(char)
                substring = substring[idx+1:]+char
                
        return max(len(substring), maxcount)

접근 방식:

1. 제일 긴 substring을 찾기 위해서는 빈 substring을 만든다.
2. 인자로 받은 string s 안에 알파벳 char 을 한개씩 for loop를 통해 확인한다.
3. 만약 substring 안에 지금 보고있는 알파벳 char가 없다면 substring에 붙여준다.
4. 만약 substring 안에 지금 보고있는 알파벳 char가 있다면

• 지금까지 이어온substring의 길이와 maxcount중에서 더 큰 길이를 maxcount로 업데이트한다.

• substring안에 지금 보고있는char이 이미 있는 상황이기 때문에 그 char 다음부터 substring을 이어주어야한다.
  그러기 위해서는 idx 변수에 substring안에 이미 있던 char의 인덱스를 저장해준다.

• substring을 idx+1 부터 이어주고, 끝에 지금 for loop에서 보던 char 를 붙인다.

5. 마지막으로len(substring)와 maxcount중에서 더 큰 값, 즉 제일 긴 substring의 길이를 리턴한다.

여담

알고리즘 너무 어렵다. 흑흑...