[알고리즘] Longest Substring Without Repeating Characters

Leetcode의 Longest Substring Without Repeating Characters 문제를 풀어보도록 하겠습니다.

문제

문자열이 주어졌을 때 중복되는 문자를 포함하지 않는 가장 긴 구간의 길이를 구하라.

예제

  • 입력: “abcabcbb”, 출력: 3

  • 입력: “bbbbb”, 출력: 1

  • 입력: “pwwkew”, 출력: 3

마지막 예제의 출력이 3인 이유는 중복되는 문자를 포함하지 않는 가장 긴 구간은 wke이기 때문입니다. 참고로 pwke는 조건을 만족하지 않습나다. 왜냐하면 연속되는 구간이 아니기 때문입니다. (a subsequence but not a substring)

풀이

먼저 가장 단순하게 생각할 수 있는 방법은 주어진 문자열에서 만들 수 있는 모든 경우의 부분 문자열을 구하는 것 입니다. 그 다음, 각 부분 문자열이 중복되는 문자를 포함하는지 검사하면 됩니다. 하지만 이 방법은 모든 경우의 부분 문자열을 구하는데 O(N^2) 시간이 소요되고, 중복되는 문자를 포함하는지 검사하는데 O(N)의 시간이 걸리기 때문에 총 O(N^3) 시간 복잡도를 가지는 매우 비효율적인 알고리즘입니다.

좀 더 생각을 해보면 불필요한 연산을 대폭 줄일 수 있습니다. 인덱스 s에서 시작하고 인덱스 e에서 끝나는 부분 문자열이 중복되는 문자를 포함하고 있지 않다면, 인덱스 s에서 시작하고 인덱스 e + 1에서 끝나는 부분 문자열에 중복되는 문자가 있는지 검사할 때는 전체 문자열을 모두 전수 검사하지 않아도, 새롭게 추가된 인덱스 e + 1에 위치한 문자가 기존 se 사이에 문자들과 중복되는지만 확인하기만 하면 됩니다.

새롭게 추가된 문자가 기존에 있던 문자들과 중복되는지 확인하는데 어떤 자료구조를 사용하면 좋을까요? 네! 바로 set를 사용하면 O(1) 복잡도로 이 작업을 수행할 수 있습니다.

그리고 만약 새롭게 추가된 문자가 중복될 경우에는 어떻게 해야할까요? 중복이 사라질 때 까지 기존의 문자들을 앞에서부터 제거해나가면 됩니다. set 자료구조는 원소 추가(add()) 뿐만 아니라 원소 제거(remove()) 연산도 제공하기 때문에 이 경우에도 딱 맞게 사용이 가능합니다.

구현

부분 문자열의 시작과 끝을 가리키는 두 개의 인덱스 포인터 se를 사용하는 흔히 sliding window라고 불리는 기법을 사용하여 구현하도록 하겠습니다. 문자가 중복되지 않는 한 sliding window를 오른쪽 방향으로 확장해나가면서 set 자료구조에 문자들을 추가해 나갑니다. 중복되는 문자가 나타나면 sling window를 문자 중복이 없어질 떄까지 왼쪽부터 줄여나갑니다.

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
def lengthOfLongestSubstring(self, text: str) -> int:
max_len, s, e = 0, 0, 0
seen = set()
while s < len(text) and e < len(text):
if text[e] in seen:
seen.remove(text[s])
s += 1
else:
seen.add(text[e])
max_len = max(max_len, e - s + 1)
e += 1
return max_len

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import java.util.*;

class Solution {
public int lengthOfLongestSubstring(String text) {
Set<Character> seen = new HashSet<>();
int maxLen = 0, s = 0, e = 0;
while (s < text.length() && e < text.length()) {
if (seen.contains(text.charAt(e))) {
seen.remove(text.charAt(s++));
} else {
seen.add(text.charAt(e++));
maxLen = Math.max(maxLen, e - s);
}
}
return maxLen;
}
}

복잡도

N을 주어진 문자열의 길이라고 했을 때, 위 알고리즘은 다음의 복잡도를 가집니다.

  • 시간: O(N)
  • 공간: O(N)

하나의 while 루프를 사용하여 시작 인덱스와 끝 인덱스 중 하나를 계속해서 증가시켜나가기 때문에 O(2N) = O(N)의 시간 복잡도를 가지게 됩니다.
그리고 하나의 set 자료구조에 중복되는 문자가 하나도 없을 경우, 최대 N개의 문자를 저장할 수 있기 때문에 O(N)의 공간 복잡도를 가지게 됩니다.

문제 출처

공유하기