[알고리즘/Python] LeetCode 3. Longest Substring Without Repeating Characters.

📑 1. 문제 이해

https://leetcode.com/problems/longest-substring-without-repeating-characters/?envType=study-plan-v2&envId=top-interview-150 

Longest Substring Without Repeating Characters - LeetCode

이 문제는 주어진 문자열의 중복이 없는 부분 문자열 중 가장 긴 부분 문자열의 길이를 구하는 문제입니다. 문자열은 영문자 소문자, 숫자, 공백, 특수문자를 포함할 수 있으며 빈 문자열 ""일 수도 있습니다. 

☑️ 테스트케이스

문제에서 주어진 테스트 케이스는 다음과 같습니다.

 

1. Example1: s = "abcabcbb"

    - 반복되는 문자가 있습니다.

2. Example2: s = "bbbbbbb"

    - 모든 문자가 중복됩니다.

3. Example3: s = "pwwkew"

    - 조건을 만족하는 가장 긴 부분 문자열이 "wke"로 배열의 중간에 위치합니다. 

 

추가해서 살펴봐야할 테스트 케이스는 다음과 같습니다.

 

4. s= "12ab c2a."

  - 숫자와 특수문자가 포함되며 중복이 있는 경우

5. s= "12abc ."

  - 숫자와 특수문자가 포함되며 중복이 없는 경우

6. s= ""

    - 빈 문자열인 경우

💡 2. 알고리즘 설계

 부분 문자열에 대해서 살펴봐야 한다는 점에서 슬라이딩 윈도우를 떠올렸습니다. LeetCode 209. Minimum Size Subarray Sum 에서 오른쪽 포인터를 한칸씩 옮겨가며 그때마다 최소가 되는 슬라이딩 윈도우를 구했던 것을 응용할 수 있습니다. 오른쪽 포인터를 한칸씩 옮겨가며, 그때마다 중복이 없는 최대 윈도우를 구하면 됩니다.

 

1. 최대 윈도우 사이즈를 의미하는 변수 min_len을 -float('inf')로 초기화합니다. 중복이 없는 문자열을 발견하지 못했을때 혹은 빈문자열일때 0을 반환하기 위함입니다.

2. 윈도우의 시작점을 의미하는 포인터 l을 0으로 초기화합니다. d는 매 문자열이 등장한 횟수를 기록하기 위한 dict 자료형 변수입니다. duplicated는 중복된 문자의 개수를 의미합니다. 

     - 만약 부분 문자열이 'aab'인 경우 d[a] = 2이며 duplicated = 1이 됩니다.

3. 오른쪽 포인터를 0부터 오른쪽으로 한칸씩 옮깁니다. d[s[r]] > 0 이라면 중복된 문자이므로 duplicated를 1 증가시킵니다. duplicated가 0이라면 부분 문자열에 중복된 문자가 없다는 의미로 max_len을 갱신해줍니다. 단, 이전에 발견된 max_len보다 큰 경우에만 갱신해 줍니다.

4. 만약 새롭게 추가된 문자가 중복된 문자라면, 중복된 문자를 제거할때까지 포인터 l을 오른쪽으로 한칸씩 움직입니다.

5. max_len을 반환합니다. 빈 문자열의 경우, max_len이 갱신되지 않은 채로 남아있기 때문에 0을 반환하도록 합니다.

from collections import defaultdict 

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        max_len = -float('inf')

        l = 0
        d = defaultdict(int)
        duplicated = 0

        for r in range(len(s)):
            chr = s[r]
            if d[chr] > 0:
                duplicated += 1
            d[chr] += 1

            if duplicated == 0 and r - l + 1 > max_len:
                max_len = r - l + 1

            while duplicated > 0:
                d[s[l]] -= 1
                if d[s[l]] == 1:
                    duplicated -= 1
                l += 1

        return max_len if max_len > 0 else 0

시간 복잡도 및 공간 복잡도

시간 복잡도: O(N).  배열의 모든 원소는 최대 2번씩 방문됩니다(왼쪽 포인터 한번, 오른쪽 포인터 한번).

공간 복잡도: O(N). 중복된 문자가 없을 경우 d에 총 n개의 엔트리가 저장됩니다.

 

⚒️ 3. 최적화

dictionary 자료형에 문자열이 마지막으로 등장한 인덱스를 저장해서 부분 문자열의 끝이 r일때 중복이 없는 가장 긴 부분문자열의 시작을 구하는 연산을 효율화할 수 있습니다. 

 새롭게 추가된 문자가 중복된 문자일때 그 문자가 마지막으로 등장한 인덱스  + 1로 시작점을 옮기면 중복이 없는 문자열이 됩니다.

   def lengthOfLongestSubstring(self, s: str) -> int:
        max_length = 0
        start = 0

        # 마지막으로 등장한 인덱스.
        used = dict()

        for end, char in enumerate(s):
            if char in used and used[char] >= start:
                start = used[char] + 1
            else:
                max_length = max(max_length, end - start + 1)
            used[char] = end
        return max_length

시간 복잡도 및 공간 복잡도

시간 복잡도: O(N). 배열의 모든 원소는 최대 2번씩 방문됩니다(왼쪽 포인터 한번, 오른쪽 포인터 한번). 따라서, 첫번째 풀이와 같이 O(N) 복잡도를 가집니다. 하지만 left 포인터를 이동하기 위해 반복문을 사용하지 않고 used에 저장된 인덱스를 참조하므로 실제 연산횟수는 더 작을 수 있습니다.

공간 복잡도: O(N). 중복된 문자가 없을 경우 d에 총 n개의 엔트리가 저장됩니다.

---

✅ 정리

◎ 슬라이딩 윈도우를 보완하기 위해 dictionary 자료형을 쓸 수 있습니다.