Python 알고리즘 인터뷰 - 문제 30. 중복 문자 없는 가장 긴 부분 문자열

leetcode 3. Longest Substring Without Repeating Characters - https://leetcode.com/problems/longest-substring-without-repeating-characters/description/

 

예제1

입력

abcabcbb

 

출력

3

 

설명

- "abc"가 가장 긴 문자열로 길이가 3 

 

예제2

입력

bbbbb

 

출력

1

 

설명

- b가 가장 긴 문자열로 길이가 1

 

예제3

입력

pwwkew

 

출력

3

 

설명

- wke가 가장 긴 문자열로 길이가 3

 

풀이

슬라이딩 윈도우와 투포인터로 사이즈 조절하는 방법을 사용하여 문제를 해결한다.

먼저 길이 계산을 위한 시작 index를 start 변수로 초기화한다. 이후 문자열 s를 순회하면서 start와 i 간의 간격을 계산하여 최대값을 max_length로 갱신한다.

또한 문자 key, 해당 index를 value로 하여 딕셔너리 used에 저장한다. 해당 로직을 used에 해당 문자가 없을 때까지 진행한다.

이를 코드로 나타내면 다음과 같다.

used = {}
max_length = 0
start = 0
for i, ch in enumerate(s):
	if ch in used:
    	...
    else:
    	max_length = max(max_length, i - start + 1)
    
    used[ch] = index

 

현재 s[i]에 해당하는 문자 ch가 used에 존재할 경우 start를 used[ch]의 다음 위치로 이동시킨다. used는 현재 ch의 인덱스 값으로 갱신시킨다.

해당 로직은 if문에서 다음과 같이 구현된다.

if ch in used:
    start = used[ch] + 1    	
else:
    ...

used[ch] = index

 

해당 로직을 반복하면 start위치와 used의 값이 갱신되면서 최대 length값을 구할 수 있다.

여기서 주의해야할 점은 start의 값이 used[ch]값보다 작아야한다는 점이다. 예를 들어 "abcba" 문자의 경우에 위의 로직을 적용하면 다음과 같이 진행된다.

i=3에서 ch='b'가 used에 존재하므로 start = used['b'] + 1 = 2이다. 따라서 start = 2로 적용한 후 루프를 진행한다. 이 후 i=4, ch='a' 일 때 used['a'] = 0이므로 start = used['a'] + 1 = 1이 된다. 이는 start 위치가 이전으로 돌아가게 되므로 예외처리를 해주어야한다.

코드에 다음과 같이 start보다 used[ch]가 큰 경우에만 start 위치를 이동하도록 수정한다.

def lengthOfLongestSubstring(self, s):
    used = {}
    max_length = 0
    start = 0
    for i, ch in enumerate(s):
        if ch in used and start <= used[ch]:
            start = used[ch] + 1
        else:
            max_length = max(max_length, i - start + 1)

        used[ch] = i

    return max_length

 

전체 코드는 다음과 같다.