[leetcode] longest-substring-without-repeating-characters

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

Longest Substring Without Repeating Characters - LeetCode

1. 슬라이딩 윈도우로 한 칸씩 우측으로 이동하면서

2. 윈도우 내에 모든 문자가 중복이 없도록

3. 투 포인터로 윈도우 사이즈를 조절하면서 풀이한다.

def lengthOfLongestSubstring(s):
    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)

        print("1", used)
        # 현재 문자의 위치 삽입
        used[char] = index

        print("2", used, index, char, start)
    return max_length

풀면서 중요하다고 생각했던 조건은 start <= used[char] 이였다.

테스트 케이스 예시로 "tmmzuxt" 이 경우에 저 조건을 추가해주지 않으면
마지막 t 문자를 살필 때, start는 2이고, max_length = 4('mzux')인 상태에서 if char in used에 걸리게 되어,
max_length = 5('mzuxt')로 갱신해주지 못한다.

 

따라서, 중복되는 문자가 현재 윈도우 내에 존재하는지 하지않는지 걸러주는 조건을 추가해주어야 통과할 수 있다.