[리트코드(LeetCode)] 3번 Longest Substring Without Repeating Characters

문제

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

Longest Substring Without Repeating Characters - LeetCode

중복 문자가 없는 가장 긴 부분 문자열의 길이를 구하는 문제다.

예시

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.

풀이

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

 

- 슬라이딩 윈도우와 투 포인터로 사이즈 조절해서 가장 긴 문자열의 길이를 구한다.
- 중복이 발생하면 현재 부분 문자열의 시작 위치를 중복된 문자의 바로 다음 위치로 갱신한다.

- 중복이 발생하지 않은 경우, 현재 문자를 포함한 부분 문자열의 길이를 계산하여 최대 값을 갱신한다.

 

참조 : 박상길, 파이썬 알고리즘 인터뷰  https://github.com/onlybooks/algorithm-interview