[리트코드] Longest Substring Without Repeating Characters(python)

리트코드, Longest Substring Without Repeating Characters_중복 문자가 없는 가장 긴 서브 문자열

TL;DR

• 딕셔너리(dictionary)
• 두 개의 포인터(투 포인터, two pointer)를 활용한 슬라이딩 윈도우(sliding window)를 구현할 수 있는지

문제 분석

1. 주어진 문자열 s에 대해, 중복 문자가 없는 가장 긴 서브 문자열의 길이를 찾아라.

 

- 해결해야 하는 문제 조건에 대해서 말하고 있다.

- 여기서 주의해야할 점은 서브 문자열이라는 것이다. 이 부분에 대해서는 입출력 형태에서 확인하도록 하겠다.

입출력 형태

입출력 예시

 

- 가장 먼저 생각할 수 있는 방법은 `collections.Counter` 또는 `set`으로 변환하여 중복을 제거하는 방법이다. 단, 이 방법으로는 문제를 해결할 수 없다. 그 이유는 서브 문자열을 구해야 하기 때문이다.

- 예시 3번을 통해 이를 확인할 수 있다. 주어진 문자열 "pwwkew"에서 중복을 제거하면 "pwke"가 되어 정답이 4가 되어야 할 것 같다. 하지만, "pwke"는 서브 문자열이 아니다. 주어진 문자열 내에는 "pwke"라는 문자열이 존재하지 않는다.

  - 주어진 문자열의 서브 문자열은 "pww", "wkew" 등과 같이 말 그대로 문자열의 일부분을 의미한다.

풀이

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        used = collections.defaultdict()
        max_length = start = 0
        
        for i, c in enumerate(s):
            if c in used and start <= used[c]:
                start = used[c] + 1
            else:
                max_length = max(max_length, i - start + 1)
                
            used[c] = i
            
        return max_length

 

- 서브 문자열 제작에 사용된 문자를 key, 사용한 문자의 인덱스를 value로 하는 딕셔너리 used를 사용한다.

- 두 개의 포인터를  활용한 슬라이딩 윈도우 방식으로, 이 때, start는 서브 문자열의 시작 지점을 나타내고, i는 증가하며 슬라이딩 윈도우에 해당하는 서브 문자열을 늘려나간다.

- 주어진 문자열의 구성 문자를 조회하며 사용한 문자열인지 아닌지 딕셔너리에서 조회를 통해 확인한다.

- 만약 이미 조회한 문자열임이 딕셔너리 조회를 통해 확인된다면, 슬라이딩 윈도우의 시작지점을 변경한다.

- 서브 문자열을 늘려가며 슬라이딩 윈도우에 넣고, 새로운 서브 문자열이 만들어질 때의 최대 길이를 누적해나가면 된다.

- 예시 3의 경우 start가 3, 즉 슬라이딩 윈도우에 "wke"가 들어왔을 때 최초로 가장 긴 길이의 서브 문자열을 만들게 된다.