30. Longest Substring Without Repeating Characters

리트코드

• 중복 문자가 없는 가장 긴 부분 문자열(substring)의 길이를 리턴하라.

  • 문자열 S의 부분 문자열이란, 문자열의 연속된 일부를 의미한다.

    예를 들어, "aek", "joo", "ekj"는 "baekjoon"의 부분 문자열이고, "bak", "p", "oone"는 부분 문자열이 아니다.

1. 슬라이딩 윈도우와 투 포인터로 사이즈 조절

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        used = {}
        max_length = start = 0
        
        for index, char in enumerate(s):
            #이미 등장했던 문자라면 'start' 위치 갱신
            if char in used and start <= used[char]:
                start = used[char] + 1
            
            else: #최대 부분 문자열 길이 갱신
                max_length = max(max_length, index - start + 1)
                
            #현재 문자의 위치 삽입
            used[char] = index
            
        return max_length
            

• s = "abcabcbb"인 경우를 가정해보자

• 슬라이딩 윈도우로 한 칸씩 우측으로 이동하면서 윈도우 내에 모든 문자가 중복이 없도록 투 포인터로 윈도우 사이즈를 조절하면서 풀이해보면 결과는 다음과 같다.

<부분 문자열을 찾는 투 포인터 풀이>

• 이 그림에는 슬라이딩 윈도우의 각 단계별로 중복 문자가 없는 윈도우의 최대 길이를 순서대로 표시했다.

  • 이 경우 세 번째부터 길이가 3으로 최대 길이가 되며, 이 길이는 여섯번째까지 변경 없이 계속 유지된다.

  • 정답은 3이다.

정답을 찾는 과정을 코드로 구현해보자.

• 먼저, 투 포인터로 문제를 풀이하되, 포인터 2개 모두 왼쪽에서 출발한다.

  • 각각 왼쪽 시작점에서 출발해 두 번째 포인터 (여기서는 index 변수)는 계속 오른쪽으로 확장한다.

  • 만약, 이미 등장한 문자라면 used에 있을 것이고, 이 경우 첫 번째 포인터인 start를 used[char] + 1 위치로 갱신한다.

    • 등장하지 않았던, 처음 문자라면 매번 max() 부분 문자열의 길이를 확인하면서 더 큰 값인 경우 갱신한다.

• 세 번째 위치부터는 계속 최댓값인 3을 유지하게 된다.

  • 또한, 현재 문자의 위치는 게속 갱신해준다.

• 이제 used[char]는 현재 문자를 키로하는 해시 테이블이며, 여기에는 현재 위치를 값으로 삽입한다.

  • 즉, start = used[char] + 1는 현재위치 + 1이 되며,
    이미 등장했던 문자인 경우 왼쪽 포인터인 start를 현재 위치까지 옮기게 된다.
    
    
    

  • 하지만, 이미 등장했다고 무작정 옮기는 것은 곤란하다. 현재 슬라이딩 윈도우의 바깥에 있는 문자는 예전에 등장한 적이 있더라도 지금은 무시해야 하기 때문이다.

    • 따라서 비교 구문에 다음과 같이 and 이후에 조건 start <= used[char]를 추가한다.

    • 이렇게 하면 슬라이딩 윈도우 안쪽에 있는 중복 문자에 대해서만 True 처리가 될 것이다.