문제
풀이
처음에는 2중 루프로 풀었다.
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
record = 0
for i in range(len(s)):
for j in range(i, len(s)):
substring = s[i:j+1]
if len(substring) == len(set(substring)):
record = max(record, len(substring))
else:
break
return record
별 생각 없이 모든 경우의 수를 다 따지면 쉽게 풀 수 있다. 다만 시간복잡도가 $O(nlogn)$, 최악의 경우 $O(n^2)$이 된다.
투 포인터로 풀면 더 간단하다.
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
used = {}
head = -1
record = 0
for idx, char in enumerate(s):
if char in used and head <= used[char]:
head = used[char]
else:
record = max(record, idx - head)
used[char] = idx
return record
다만 중복된 문자를 받을 경우 head를 어디에 둬야하는지 생각을 잘 해야 한다.