[LeetCode] 3. Longest Substring Without Repeating Characters (c++)

 

 

 

문제

 

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

Longest Substring Without Repeating Characters - LeetCode

 

 

풀이

 

 

난이도: Medium 

 

일단 본인의 풀이를 소개하고 나서 더 간단한 방법을 설명하겠다.

 

먼저, 문자열의 각 (idx 번째)문자로 부터 오른쪽으로 이동하여 가장 가까운 같은 문자가 나오는 거리를 minDistanceFromSameChar[idx] 라고 하자.

 

이를 처음에 만들어주기 위해 2중 for문을 만들어 주자.

 

memset(minDistanceFromSameChar, -1, sizeof(minDistanceFromSameChar));

for (int idx =0; idx<s.length(); ++idx) 
	for (int dist = 1; dist + idx < s.length(); ++dist) 
		if (s[idx] == s[dist + idx]) {
			minDistanceFromSameChar[idx] = dist;
			break;
		}

만약 끝까지 같은 문자가 나오지 않는다면 -1로 유지된다.

 

예를 들어 "abcabcbb"는 다음과 같은 minDistanceFromSameChar이 만들어진다.

a	b	c	a	b	c	b	b
3	3	3	-1	2	-1	1	-1

 

 

이제 minDistanceFromSameChar를 이용하여 답을 구해보자.

 

가장 처음의 a에서부터 subString이 시작되면,  minDistanceFromSameChar를 통해 최대 3의 길이를 가질 수 있음을 알 수 있다.

 

이번에는 두번째 a에서 시작해보자.

두 번째 a의  minDistanceFromSameChar는 -1으로 끝까지 같은 문자가 나오지 않아, 최대 길이는 문자열의 끝이 될 가능성이 있다. 

하지만 다음 칸에 등장하는 두 번째 b는 2칸 이후 같은 문자가 등장한다.

따라서 두번째 b를 포함하는 subString의 최대 길이는 b의 다음인 c까지이다.

 

이런 식으로 idx번째 문자부터 시작하여 포함되는 문자들의 minDistanceFromSameChar통한 최대 길이 가지만을 탐색해보는 알고리즘을 구현하였다.

 

 

 

코드

 

 

 

 

 

 

더 빠른 풀이

 

 

위의 풀이 코드는 N^2의 복잡도를 가진다.

(엄밀히 말하면 char형은 256가지를 나타내므로 N^2까진 아니다.)

 

실제로 속도는 제출 표본에서 하위 28%를 기록했다.

 

본인의 풀이는 각 문자가 동일한 문자가 다시 나오기까지의 거리 저장하기 위해 minDistanceFromSameChar를 미리 계산하였다. 거기에다 minDistanceFromSameChar를 저장하기 위해 문자열의 최대길이인 50000만큼의 int형 배열의 공간도 소모한다.

 

 

이번에는 O(N)의 시간 복잡도에, 공간 복잡도도 낮은 간단한 풀이을 확인 하자.

 

 

풀이 원본 코드 링크

https://leetcode.com/problems/longest-substring-without-repeating-characters/discuss/1737/C%2B%2B-code-in-9-lines.

 

 

 

일단 문자열은 char형이 연결된 형식이므로, 모든 문자의 종류는 256개이다.

vector<int> dict(256, -1);

 

dict은 각 문자가 중복되는 시점에서 해당 위치를 저장한다. 않는 최소 시작 지점을 저장한다.

예를 들어 "abcabcbb" 에서의 dict은 다음과 같이 저장된다.

 

위치	0	1	2	3	4	5	6	7
문자	a	b	c	a	b	c	b	b
변경 전 dict	dict[a] = -1	dict[b] = -1	dict[c] = -1	dict[a] = 0	dict[b] = 1	dict[c] = 2	dict[b] = 4	dict[b] = 6
변경 후 dict	dict[a] = 0	dict[b] = 1	dict[c] = 2	dict[a] = 3	dict[b] = 4	dict[c] = 5	dict[b] = 6	dict[b] = 7

 

 

 

초기에는 -1이 subString의 시작 지점(start)이 된다.

 

이제 문자열을 가장 왼쪽부터 오른쪽으로 하나씩 진행한다.

 

첫 번째 c 지점에서는 아직  c를 만난 적이 없기 때문에 dict[c]는 -1으로 start와 같아 start는 변하지 않는다.

이후 dict[c] = 2(해당 위치)로 바꿔주고 maxLen은 start부터의 거리인 3이 된다.

 

두 번째 a를 만나는 지점을 생각해보자.

dict[a]에는 0이 저장되어 있어 start보다 크다.

따라서 start가 0이 되어 첫 번째 a로부터 두 번째 a까지의 거리가 maxLen이 되는 식이다. 

 

이를 반복하면 같은 문자의 중복 위치로 subString의 길이를 O(N)에 계산할 수 있다.