[LeetCode] 3. Longest Substring Without Repeating Characters (파이썬)

3. Longest Substring Without Repeating Characters - 파이썬 풀이

• 해당 문제 링크

< 목차 >

1. 문제접근 아이디어
2. 구현코드

문제접근 아이디어

• 일단 문자열의 길이가 50,000개 정도이기 때문에 순차적인 탐색을 해도 괜찮을 것 같다.
• 순차적으로 비교를 하다가 지금 가지고 있는 subString안에 같은 문자가 존재하면 해당 문자까지 빼주고 중복되지 않는 문자부터의 subString에 현재 문자를 더해서 다시 비교해준다.
• 같은 문자가 나오면 최대값과 비교해서 갱신한다.

구현코드

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        if s == "":
            return 0
        start = 0
        maxLength = 1
        subString = dict()
        for end, char in enumerate(s):
            if subString.get(char, 0):
                maxLength = max(maxLength, len(subString))
                for i in range(len(subString)):
                    del subString[s[start]]
                    start += 1
                    if not subString.get(char, 0):
                        subString[char] = 1
                        break
            else:
                subString[char] = 1
        maxLength = max(maxLength, len(subString))
        return maxLength

위는 처음 코드를 짰을 때 코드이다.

• 중복되는 문자를 만나면 길이를 비교하고 딕셔너리 안에 중복되는 문자까지 삭제를 시키면서 start를 고쳐나가서 딕셔너리 길이를 이용해서 최대값을 비교하는 모습이다.

다음 코드는 조금 더 간략하게 수정을 거친 코드이다.

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        if s == "":
            return 0
        start = 0
        maxLength = 1
        subString = dict()
        for end, char in enumerate(s):
            if subString.get(char, 0) and start <= subString[char]:
                start = subString[char]
            else:
                maxLength = max(maxLength, end - start + 1)
            subString[char] = end + 1
        return maxLength

• 처음 코드에서는 for문을 돌려서 중복되는 문자까지 빼주는 방법을 사용했다.
• 하지만 슬라이딩 윈도우에서 start라는 처음을 지정하는 인덱스가 있기 때문에 딕셔너리에 키와 밸류를 넣을 때 밸류에 해당 인덱스 값을 넣어줌으로써 더 쉽게 접근하게 바꾸었다.
• 이렇게 되면 딕셔너리 안에는 값이 계속 존재하기 때문에 만약 start보다 더 작은 인덱스에 같은 문자가 있다면 그건 상관쓰지 않게 하기 위해서 조건문에 start <= subString[char] 라는 구문을 넣었다.
• 이제는 딕셔너리 안에 상관쓰지 않아도 되는 문자들이 들어있기 때문에 len()을 이용해서 최대 값을 비교할 수는 없고 인덱스를 이용해서 길이를 구해준다.