[리트코드] 3. Longest Substring Without Repeating Characters

3. Longest Substring Without Repeating Characters

문제

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

제한사항

• 0 <= s.length <= 5 * 104
• s consists of English letters, digits, symbols and spaces.

풀이

한 개씩 붙여가면서 부분 문자열 만들기

현재 문자가 만든 부분 문자열에 포함되어 있으면 부분 문자열 길이 갱신하고 포함되지 않을 때까지 앞에서 하나씩 자르기

예) "abcabcbb"

a

ab

abc

a가 이미 포함되어 있으므로 앞에 자르기

bca

b가 이미 포함되어 있으므로 앞에 자르기

cab

.

.

마지막에 부분문자열 길이와 이전에 저장된 값 한번 더 비교

("au" 처럼 wihle 문 실행되지 않고 종료될 경우를 대비)

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        
        sub_str = ""
        answer = 0
        
        for end in range(len(s)):
            while s[end] in sub_str:
                answer = max(len(sub_str), answer)
                sub_str = sub_str[1:]
            
            sub_str += s[end]
            
        answer = max(len(sub_str), answer)
        return answer

슬라이드 윈도우 방식

start와 end를 0에 놓고 end를 움직인다.

해시맵을 사용해 문자열의 중복을 체크한다.

반복된 문자열이 현재 window에 포함되지 않은 경우 상관 없으므로 무시한다.

반복된 문자열이 현재 window에 포함된 경우 start를 해당 위치 앞으로 옮겨서 windwo에서 제거한다.

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        
        max_length, start = 0, 0
        checked = {}
        
        for end in range(len(s)):
            if s[end] not in checked: # 처음 나온 문자일 때
                max_length = max(max_length, end - start + 1)
            
            else: # 반복된 문자일 때
                if checked[s[end]] < start: # 반복된 문자열이 현재 window에 포함되지 않을 경우
                    max_length = max(max_length, end - start + 1)
                else: # 반복된 문자열이 start 다음일 경우 해당 위치로 start 이동
                    start = checked[s[end]] + 1
            
            checked[s[end]] = end
                
                
        return max_length