3. Longest Substring Without Repeating Characters
Table of Contents
Description
문제는 간단하다. 주어진 문자열 s에 대해 반복되는 문자가 없고 가장 긴 substring을 찾으면 된다.
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.
Constraints
0 <= s.length <= 5 * 10^4
Brute Force
처음에는 단순하게 brute force로 중복이 생기면 해당 substring의 길이를 반환하는 함수를 만들고 문자열들을 하나씩 이동해 나가며, max함수를 이용해 제일 긴 문자열을 반환하도록 구현하였다.
Code
class Solution:
def longestSubstringLength(self, s: str) -> int:
l = []
digit = 0
sl = []
sl[:] = s
for c in sl:
if c in l:
return digit
else:
l.append(c)
digit += 1
return digit
def lengthOfLongestSubstring(self, s: str) -> int:
ans = 0
for i, v in enumerate(s):
ans = max(ans, self.longestSubstringLength(s[i:]))
return ans
Result
하지만 해당 알고리즘의 경우 시간 복잡도가 O(n^2) 로 input의 max 제한이 10^4이기 때문에 10^8까지 연산이 될 수 있어 좋은 퍼포먼스를 낼 수 없는 알고리즘이다.
따라서, 좀 더 최적화 할 수 있는 방안을 찾던 중 Two Pointer라는 테크닉을 알게 되었고 다음과 같이 개선하였다.
Two Pointer
Two Pointer란 start, end 2개의 포인터를 설정하여 해당 2개의 포인터를 이동해 나가며, 기존의 값들을 재사용하며 문제를 해결할 수 있는 테크닉이다.
일종의 memoization이며, DP와 다른 점은 모든 상태를 저장해 놓지는 않는다.
[start, end] 구간의 길이가 상수값으로 고정되면 sliding window라는 테크닉으로 불리는 듯 하다.
Code
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
ans = 0
start = 0
end = 0
strSet = set()
sl = []
sl[:] = s
for i, c in enumerate(s):
if c in strSet:
ans = max(ans, end - start)
for subIdx in range(start, end):
subChar = s[subIdx]
if subChar in strSet:
strSet.remove(subChar)
if c == subChar:
strSet.add(c)
start = subIdx + 1
end = i + 1
break
else:
strSet.add(c)
end += 1
ans = max(ans, end - start)
return ans
Result
쉽게 해당 알고리즘을 설명하면, set에 문자들을 저장해가며 중복이 발생하면 다시 start부터 중복된 문자의 위치까지 조회하며 set에서 문자를 삭제한다.
그 후 start와 end 포인터를 재설정하며, 답을 구하게 된다.