[LeetCode] 3. Longest Substring Without Repeating Characters - Python

[LeetCode] 3. Longest Substring Without Repeating Characters - Python

 

Longest Substring Without Repeating Characters - LeetCode

 

 

문제

문자열 s가 주어질 때, 중복되는 문자가 없는 가장 긴 문자열의 길이를 반환하세요.

예를 들어 s = "abcabcbb" 라면, 중복되지 않는 가장 긴 문자열은 "abc"이므로 3을 반환합니다.

 

 

아이디어

1) 먼저, 중복 문자인지를 판별하기 위한 딕셔너리를 만든다.

2) 문자를 차례대로 탐색하면서 현재 문자가 이미 등장했는지 판별하고, 등장했다면 그 문자가 처음 등장한 위치 + 1로 이동해서 다시 시작한다.

3) 현재 문자가 아직까지 나오지 않았으면 문자열 길이를 저장하는 변수에 1을 더해준다.

 

코드

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:

        used = {};
        max_length = 0;
        start = 0

        for idx, char in enumerate(s):
            if char in used and start <= used[char]:    # 같은 문자열이 2번째 등장한 경우
                start = used[char] + 1  #첫번째 등장한 지점 이후로 start 갱신

            else:  # 빈 경우, 아직 등장하지 않은 경우, start 이후 1번만 등장한 경우
                max_length = max(max_length, idx - start + 1)


            used[char] = idx  # 현재 등장한 위치로 갱신
            # 여기서 갱신해줘야 2번째 나왔을 때 찾게됨(start보다 idx가 크기때문에)

        return max_length