[leetcode] Longest Substring Without Repeating Characters (swift)

문제

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

Longest Substring Without Repeating Characters - LeetCode

문제 요약 

반복되는 문자를 제외하고 가장 긴 부분 문자열을 구하는 문제입니다. 여기서 부분 문자열이란 원본 문자열에서 뽑아낼 수 있는 연속적인 문자열을 의미합니다. abcabcbb일 경우, abc가 반복되는 문자를 제외하고 가장 긴 부분 문자열입니다. pwwkew일 경우, pwke가 가장 긴 부분 문자열이 될 수 없는 이유는 연속적이지 않기 때문입니다. 따라서 wke가 가장 긴 부분 문자열이 됩니다. 

풀이

처음 떠오르는 풀이법은 문자열의 길이를 N이라고 할 경우, 각 문자를 시작점으로 생각하여 반복되는 문자가 나올 때까지 카운팅하고 각각의 경우를 모두 비교하여 가장 긴 문자열일 때의 길이를 구하는 방식입니다. 하지만 이 방법의 시간복잡도를 생각해봅니다. abcdefghijklmnop#&!^#(....와 같이 모든 문자가 다른 문자열일 경우, 각 문자마다 모든 문자들과 비교하게됩니다. a는 bcdefg.... b는 cdefg.... 와 같이 비교하게 되면서 결국 (N-1) + (N-2) + (N-3) + ... + 2 + 1 = (N-1)(N-2)/2 번 비교가 일어나게 됩니다. 즉, 문자열의 길이가 N이라고 할 때 최악의 경우 O(N^2)라는 것을 알 수 있습니다.

 

다른 방식은 index를 이용하는 방식입니다. 부분 문자열은 문자열 내의 연속적인 문자들의 집합입니다. 따라서 부분 문자열의 시작점만 안다면, N번 순회하면서 가장 긴 부분 문자열의 길이를 구할 수 있습니다. (현재 index - 부분 문자열의 시작점 + 1)이 부분 문자열의 길이가 됩니다. 

 

부분 문자열의 시작점을 구하는 방식은 character의 index를 저장하는 딕셔너리 자료구조를 이용할 수 있습니다. abcabcbb와 같은 경우 2번째 index까지 순회했을 때 딕셔너리는 [a: 0, b:1, c:2]와 같이 저장됩니다. 3번째 index인 a를 만난다면 [a: 3]으로 업데이트하는 동시에 부분 문자열의 시작점을 0(이전에 나온 index) + 1 로 업데이트합니다. 시작점을 업데이트할 때 주의할 점은 항상 기존 시작점과 업데이트할 새로운 시작점과 비교하여 더 큰 수를 할당해야 합니다. 왜냐하면 abcbbba 와 같이 b가 연속적으로 나올 경우 부분문자열의 시작점은 이미 업데이트가 되었기 때문입니다. 

 

풀이 코드 1

아래는 시간 복잡도가 O(N^2)가 되는 풀이입니다.

 

이 풀이는 483ms 걸리고 정말 느립니다. 두번째 풀이 방법으로 8ms만의 시간으로 O(N)의 시간복잡도로 해결할 수 있습니다.

풀이 코드 2