[Python] Leet code 3. 중복 문자 없는 가장 긴 부분 문자열 (Longest Substring WIthout Repeating Characters)

 

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

 

중복 문자가 없는 가장 긴 부분 문자열의 길이를 리턴하라

 

 

입출력 예시

Example 1:

Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

Example 2:

Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Example 3:

Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.

 

문제해결방법 - (서칭 참조)

 

유튜브에서 우연히 보고 풀이법을 생각해보는데, 간단한 듯 하면서 잘 되지 않았다.

투 포인터랑 딕셔너리를 이용하면 되겠다는 생각을 하긴 했는데, 세부 구현이 잘 떠오르진 않았다.

 

그래도 그렇게 복잡한 문제는 아니여서 여러 시행착오 끝에 할 수는 있겠단 생각이 들었지만, 구글 서칭을 참조해버림..

 

 

1. 딕셔너리 자료구조에 반복문을 돌고 있는 문자열이 없으면 딕셔너리에 넣고, 문장에서의 마지막 위치가 갱신되게끔 한다.

 

2. 같은 문자가 나오면 포인터용 변수의 위치에서부터 다시 카운팅하는 것이다. 결과적으로 그 후부터 중복 문자가 없다면, i+1(지금까지 문장의 길이) - 포인터용 변수(중복후 갱신된 새로운 위치)로 maxlen이 계속 갱신될 것이다.

 

index	0	1	2	3	4	5
String :	'P	W	W	K	E	W'
start	0	0	2	2	2	3
length (i+1-start)	1	2	1 (maxlen은 2인 상황)	2	3	1
dictionary	{'P' : 0}	{'P' : 0, 'W' : 1}	{'P' : 0, 'W' : 2}	{'P' : 0, 'W' : 2, 'K' : 3}	{'P' : 0, 'W' : 2, 'K' : 3, 'E' : 4}	{'P' : 0, 'W' : 5, 'K' : 3, 'E' : 4}

< 중복 문자를 만났을 때, start가 갱신되어 i+1-start이 중복문자가 없는 가장 긴 문자열의 길이가 된다.>

 

 

- 코드

import sys
input = sys.stdin.readline

a = 'pwwkew'

def solution(a):
	if len(a) == 1:
		return 1
	dic = {}
	start = 0
	maxlen = 0
	for i, s in enumerate(a):
		if s in dic:
			start = max(start, dic[s] + 1)
		dic[s] = i
		maxlen = max(maxlen, i + 1 - start)
	return maxlen
print(solution(a))