[해시 테이블] 30 중복 문자 없는 가장 긴 부분 문자열(Longest Substring Without Repeating Characters)

<LeetCode 문제>

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

Longest Substring Without Repeating Characters - LeetCode

중복 문자가 없는 가장 긴 부분 문자열(substring)의 길이를 리턴하는 문제입니다.

<풀이>

모든 substring을 탐색하여 시간복잡도 O(n²)으로 time out이 날것으로 예상했지만, 통과된 코드는 다음과 같습니다.

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        if len(s)<=1: #길이 0,1일때 빠르게 return
            return len(s)
        
        maximum = -sys.maxsize #최대값 갱신해나가기 위해
        
        for i in range(len(s)):
            now_set = set() #등장했는지 여부를 알기위해 hash기반 set사용
            
            for j in range(i,len(s)):
                if s[j] in now_set: #set이 hash기반이므로 시간복잡도 O(1)
                    j-=1 #바로 전 인덱스까지만이므로
                    break
                now_set.add(s[j]) #등장했다면 set에 추가
            
            if maximum < j-i+1: #최대값 갱신
                maximum = j-i+1
        
        return maximum

 

여기서 최대값을 갱신하는 부분을 maximum=max(maximum, j-i+1)로 단순화할 수 있습니다.

문제에서 n이 최대 5*10⁴으로 n²은 25*10⁸이 되어 시간초과가 나야하는데, 운좋게 통과된 것 같습니다.

 

슬라이딩 윈도우와 투 포인터로 윈도우 사이즈를 조절하면서 풀이하면 O(n)의 풀이가 가능합니다.

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        used={}
        max_length = 0
        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 # (key:현재문자, value: index)로 추가
        
        return max_length

 

max_length을 0으로 설정하여 길이가 0인 문자열이 들어올때 0을 반환할 수 있게 했습니다.

<학습내용>

1. python의 for i in ..에서 i는 for문이 끝나도 사용가능. 지역변수 아님! (링크참조)
2. in연산자의 시간복잡도는 list, tuple은 전체순회이므로 O(n)이고, set, dictionary는 해쉬기반이므로 O(1).

<학습이 필요한 내용>

1. 슬라이딩 윈도우, 투 포인터 추가 학습