[DSA][Sliding Window] 01. Longest Substring Without Repeating Characters

LeetCode 3

 

01. Longest Substring Without Repeating 

Given a string s, find the length of the longest substring without duplicate characters.

 

 

[질문하기]

- 대소문자를 구분하나요?

- 문자열에 공백이나 특수 문자가 있을 때 어떻게 처리해야 하나요? 공백들도 중복된 문자로 간주하나요?

 

 

[아이디어]

- 문자, 인덱스를 기록해 놓고 중복된 문자가 들어오면 길이를 세는 시작점을 (인덱스 + 1)로 옮긴다.

 

 

[풀이 1] Sliding Window

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        mp = {}
        l, res = 0, 0
        
        for r in range(len(s)):
            if s[r] in mp:
                l = max(mp[s[r]] + 1, l)
            mp[s[r]] = r
            res = max(res, r - l + 1)
        return res

주어진 문자열에서 중복된 문자가 없는 가장 긴 부분 문자열을 찾기 위해 슬라이딩 윈도우(Sliding Window) 기법을 사용할 수 있다.

 

1) Dictionary를 사용하여 Index를 저장하는 방식

각 문자를 딕셔너리의 key로 저장하고, 그 값은 해당 문자가 마지막으로 등장한 인덱스이다.

R 포인터로 문자를 순회하면서 각 문자의 인덱스를 저장하다가, 중복된 문자가 나온다면 그 문자가 마지막으로 등장했던 위치를 확인하고, 포인터를 해당 위치의 다음 인덱스로 옮겨 중복된 문자가 포함되지 않도록 새로 길이를 계산한다.

 

2) Set을 사용하여 Index 저장 없이 처리하는 방식

시작(L), 끝(R) 두 포인터를 둔 후, 인덱스를 저장하는 대신 중복된 문자가 나온다면 중복되지 않을 때까지 set에 저장된 s[L]을 지우면서 L을 한 칸씩 옮겨주는 방식도 가능하다.

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        charSet = set()
        L, maxLen = 0, 0

        for R in range(len(s)):
            while s[R] in charSet:
                charSet.remove(s[L])
                L += 1
            charSet.add(s[R])
            maxLen = max(maxLen, R - L + 1)

        return maxLen

 

 

⏱️ 시간복잡도

문자열을 한 번 순회하기 때문에 O(n)의 시간 복잡도를 갖는다.

🧠 공간복잡도

최악의 경우 모든 char를 저장해야 하므로 O(n)의 공간 복잡도를 갖는다.