[Leetcode] Longest Substring Without Repeating Characters

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

---

Constraints:

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

---

풀이

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        used = {}
        max_length = start = 0
        for index,char in enumerate(s):
            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

 

결과

---

문제 풀이

슬라이딩 윈도를 활용한 투 포인터를 적용하여 풀었다. 포인터 2개는 모두 왼쪽에서 출발하고 각 왼쪽 시작점에서 출발해 두 번째 포인터 (index)는 계속 오른쪽으로 확장한다.

start = used[char] + 1

만약 등장한 문자라면 used에 있을 것이고 이럴 경우 첫 번째 포인터인 start를 used [char] + 1 위치로 갱신한다. 등장하지 않았던 처음 보는 문자라면 다음과 같이 처리한다.

else:
     max_length  = max(max_length , index - start + 1)

처음 보는 문자인 경우 매번 max함수로 부분 문자열의 길이를 확인하면서 더 큰 값인 경우 갱신한다. abc 부터는 계속 최댓값 3을 유지하게 된다. 또한 다음과 같이 현재 문자의 위치는 계속 갱신한다.

used[char] = index

start는 현재 위치 +1이 되고 이미 등장했던 문자인 경우 왼쪽 포인터인 start를 현재 위치까지 옮기게 된다. 

 

하지만 이미 등장했다고 무작정 포인터를 옮겨버리면 안 된다. 현재 슬라이딩 윈도의 바깥에 있는 문자는 예전에 등장한 적이 있더라고 지금은 무시해야 하기 때문이다. 따라서 비교 구문에 다음과 같이 and 이후에 조건 start <= user [char]를 추가해야 한다.

if char in used and start <= used[char]:

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