본 문서는 https://www.udemy.com/course/master-the-coding-interview-big-tech-faang-interviews/ 강의를 참조하여 작성되었습니다.
문제
Given a string s, find the length of the longest substring, without repeating characters.주어진 문자열 s에 대해, 문자가 겹치지 않는 부분 문자열의 최대 길이를 리턴하시오.
예시
Input: s = "abcabcbb"
Output: 3
Explanation: 문자가 겹치지 않으면서 길이가 최대인 "abc"의 길이는 3이다.제한
0 <= s.length <= 5 * 10^4
s 는 영문자, 숫자, 기호, 공백으로 이루어져 있다.풀이법
1. BRUTE FORCE
문자열의 모든 문자가 시작점이 될수 있다고 가정하고 세어나가
가장 긴 문자열을 형성하는 경우에 대해 길이를 저장해 리턴한다.
이 경우 모든 문자열 O(n) 에 대해 순차탐색 O(n) 이 이루어져
시간복잡도는 O(n^2)가 되어 사실상 사용하기 힘들다.
2. SLIDING WINDOW
dictionary / map 을 이용해 중복값을 찾고, 변수를 이용해 시작지점을 저장한다.
아래는 설명 관련 그림인데 각각의 변수는 다음과 같은 역할을 가진다.
- dictionary - 문자열의 중복을 확인하기 위한 수단이며 key는 문자 value는 문자의 위치이다
- start - 중복이 없는 문자열의 시작 위치이다.
- cnt - 각각의 문자가 중복 없는 문자열의 마지막 문자일때 최대 길이를 저장한다.
아래 이미지와 함께 설명하겠다.
첫번째 문자인 a는 dictionary에 key가 a인게 없기에 일단 중복이 아니다.
그리고 첫번째 문자이기 때문에 여기서 찾을 문자열의 제일 첫번째 문자이기도 해서 start는 0이 된다.
"a"의 길이는 1이기에 cnt엔 1이 저장된다.
이후에도 중복이 없기에 start는 바뀌지 않고 cnt는 각각 "ab" 와 "abc"의 길이가 2, 3 이므로 그 값을 넣는다.
차후 중복 검사를 위해 dictionary를 갱신하는것도 잊으면 안된다.
아래의 선은 마지막 글자를 기준으로 가장 길면서 중복단어가 없는 문자열을 의미한다.
허나 이 경우 c가 dictionary에 있으면서, 즉 중복이면서 문자열의 시작위치보다 중복 문자가 있는 위치 ( 2 ) 가 더 크다.
이 경우 중복된 위치까지의 문자들은 이 문자로 끝나는 문자열에 포함될수 없다.
그렇기에 시작지점은 중복문자가 있던 위치 + 1이 되며
cnt는 현재 위치 - 중복 문자가 있던 위치의 값 ( 3 - 2 ) 가 된다.
dictionary는 항상 새로운 위치로 갱신한다.
이때 a도 dictionary 탐색시 중복이지만, 이전에 a가 있던 위치는 새로운 문자열의 시작지점보다 앞에 있는, 전혀 상관없는 문자이기 때문에 무시해도 된다.
물론 dictionary 위치는 갱신한다.
위와 같다.
마지막 b의 경우 중복 위치 ( 5 ) 가 문자의 시작지점 ( 3 ) 보다 크기에 전체적으로 갱신하는 과정을 거친다.
이후 계산된 cnt는 생길수 있는 문자열의 최대길이의 모음이기에, 이의 최댓값을 구해 리턴하면 된다.
코드는 다음과 같다.
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
# 저장용 변수
if len(s) == 0: return 0
checker = dict()
start = 0
cnt = [0 for x in range(len(s))]
for i in range(len(s)):
# 중복이 아닐때
if s[i] not in checker:
checker[s[i]] = i
if i == 0:
cnt[i] = 1
else:
cnt[i] = cnt[i-1] + 1
else:
# 중복이지만 문자열에 포함은 안될때
if checker[s[i]] < start:
checker[s[i]] = i
cnt[i] = cnt[i-1] + 1
# 중복이면서 문자열에 포함될때
else:
cnt[i] = i - checker[s[i]]
start = checker[s[i]] + 1
checker[s[i]] = i
return max(cnt)문자열에 대해 1차원 for loop만 있기에 O(n)의 시간복잡도를 가지며 문자열의 길이만큼 저장공간이 필요하기에
O(n)의 공간복잡도를 가진다.
만약 cnt변수를 하나로 줄일수 있다면 공간복잡도는 O(1)을 가질수 있을것이다.
(2024 / 11 / 21)
복기
- 좀더 명시적으로 Sliding window 를 써봤다.
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
N, d, left = len(s), {}, 0
ans = 0
for right in range(N):
d[s[right]] = d.get(s[right], 0) + 1
while left < right and right - left + 1 != len(d.keys()):
d[s[left]] -= 1
if d[s[left]] == 0:
del d[s[left]]
left += 1
ans = max(ans, right - left + 1)
return ans