(leetcode 문제 풀이) 3번, Longest Substring Without Repeating Characters

leetcode medium 문제를 얕봤다가 큰코 다쳤다. 쉽게 해결할 수 있는 문제가 전혀 아니다. 스스로 1시간이 되도록 풀지 못해 구글링을 했다.

문제 설명
Given a string s, find the length of the longest substring without repeating characters.

Example 1
Input: s = "abcabcbb"
Output: 3 Explanation:
The answer is "abc", with the length of 3.

Example 2
Input: s = "bbbbb"
Output: 1 Explanation:
The answer is "b", with the length of 1.

Example 3
Input: s = "pwwkew"
Output: 3 Explanation:
The answer is "wke", with the length of 3. Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.

Example 4
Input: s = ""
Output: 0

조건
- 0 <= s.length <= 5 * 104
- s consists of English letters, digits, symbols and spaces.

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        ans = 0
        left_cursor = 0
        used = {}
        
        for right_cursor, char in enumerate(s):
            if char in used and left_cursor <= used[char]:
                left_cursor = used[char] + 1
            else:
                ans = max(ans, right_cursor - left_cursor + 1)
            used[char] = right_cursor
            
        return ans

위의 방법을 Sliding window라고 부르는 것 같다. for문을 2번 쓰는 것보다 시간 복잡도에서 유리하다. 

처음에 문자열에서 반복되는 문자가 나오기 전까지의 문자 개수를 세고, 반복된 문자부터 다시 문자열을 재구성하자고 생각했다. 즉 "abcabcbb"에서 "abc"까지 3개, 다음 문자열은 "abcbb"로 생각하는 것이다. 여기까진 정확히 맞았다. 

하지만 딕셔너리를 사용할 생각은 하지 못했다. used 딕셔너리를 통해 각 문자열의 인덱스를 저장하고 중복된 문자열 다음의 문자 인덱스는 left_cursor에 따로 저장했어야 했다. right_cursor는 문자열의 순차적인 인덱스고 이 둘 간의 차이가 곧 반복되지 않는 문자열의 연속 개수를 의미한다. 

아래 각 단계 출력값을 통해 과정을 확인했다.

s = "pwwkew"
ans = 0
left_cursor = 0
used = {}

for right_cursor, char in enumerate(s):
    print("right_cursor: ", right_cursor, "/ character is: ", char)
    if char in used and left_cursor <= used[char]:
        left_cursor = used[char] + 1 # 반복되는 문자 다음의 문자 인덱스 저장
    else:
        ans = max(ans, right_cursor - left_cursor + 1) # 중복 전까지 다른 문자가 연속된 최대 횟수
    used[char] = right_cursor # value값 업데이트 ex)w는 최종 인덱스 5에 위치
    print("left_cursor: ", left_cursor)
    print("answer: ", ans)
    print("used dictionary is: ", used)
    print("\n")

used 딕셔너리 w의 value 값을 잘 보기 바란다. 1 -> 2 -> 5 순서로 변경되는 것을 알 수 있고, 마지막 값은 즉 w의 최종 인덱스 위치다. 그리고 left_cursor은 반복된 문자 오른쪽에 있는 문자 인덱스를 가리킨다. 기존에 "pwwk" 에서 left_cursor는 2(=w 인덱스)였고, e가 입력된 순간 "wke"로 answer는 3이 되었다. 이후 w가 다시 입력되면 left_cursor는 3(=k 인덱스)으로 변한다. w가 다시 반복되었기 때문에 다음 문자열인 k의 인덱스를 가리키게 된다.

감이 왔는데 이걸 제대로 코드로 구현하지 못했다. 앞으로 좀 더 그림도 그리고 끄적여봐야겠다.