Leetcode - 3. Longest Substring Without Repeating Characters (파이썬)

문제 주소

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

Longest Substring Without Repeating Characters - LeetCode

내용

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

해설

문자열이 주어질 때 반복되는 문자가 나오지 않는 가장 긴 문자열을 구하는 문제이다.

즉 "abca" 가 입력으로 들어오면 (제거 대상을 굵은 글씨로 표시하였다.)

1. a -1
2. ab -2
3. abc -3
4. abca ← 이미 들어온 a 가 있으므로 Fail 이다

이경우에는 가장 긴 문자열은 abc이고 길이는 3이다. 이런 방식으로 진행하며 탐색 하면된다.

더 긴경우인 "abcabcbb" 를 예로 보자. (제거 대상을 굵은 글씨로 표시하였다.)

1. a-1
2. ab -2
3. abc -3
4. abca ←a가 들어왔으므로 맨앞의 a를 지우고 계속 진행한다.
5. bcab ←b가 들어왔으므로 맨앞의 b를 지우고 계속 진행한다.
6. cabc ←c가 들어왔으므로 맨앞의 c를 지우고 계속 진행한다.
7. abcb ←b가 들어왔으므로 b와 앞에있는 모든 문자열을 지운다.
8. cbb ←b가 들어왔으므로 맨앞의 b를 지우고 계속 진행한다.
9. b

이렇게 진행해서 가장 긴 문자열은 abc - 3자리가 된다.

방금의 예제를 확인하면서 아래 생각이 든다면 문제를 풀수 있다.

"이미 들어온 문자가 들어오면 앞에 있는 중복된 문자열까지 pop(0) 또는 popleft()를 해주면 된다!"

(성능 상 popleft를 사용한다)

코드

import collections
def length_of_longest_substring(self, s: str) -> int:
    max_len = 0

    q = collections.deque()
    for i in s:
        # 큐에 들어있지 않다면 삽입한다.
        if i not in q:
            q.append(i)
        else:
            # 큐에 들어있다면 index를 찾는다
            index = q.index(i)

            # 인덱스까지의 모든 요소를 pop 한다.
            for j in range(index + 1):
                q.popleft()

            # 다시 문자열을 넣어준다.
            q.append(i)

        # 문자열이 들어오고 나갈때 마다 최대값을 비교한다.
        max_len = max(max_len, len(q))

    return max_len


print(length_of_longest_substring('abcabcbb'))
print(length_of_longest_substring('bbbb'))
print(length_of_longest_substring('pwwkew'))

 

성능

큐에서 i가 들어있는지 확인하는 과정(if i not in q)은 시간복잡도가 O(n) 이므로

딕셔너리를 동시에 사용해서 조회한다면 복잡도를 더 줄일 수 있지 않을까?

이런 생각이 들었지만 앞의 모든 인덱스를 삭제해야 할 경우 딕셔너리에서 제거하는 경우도 비슷할 것이라 판단하였다.