LeetCode 3(Longest Substring Without Repeating Characters, Python)

1. 문제 링크

• Longest Substring Without Repeating Characters - LeetCode

2. 문제 설명

• 주어진 문자열에 포함된 문자열 중 중복된 문자가 없는 것 중 길이의 최댓값을 반환
• 예시) s = "abcabcbb"이면 "abc"가 가장 길기 때문에 3, s = "bbbbb"이면 "b"가 가장 길기 때문에 1, s = "pwwkew"이면 "wke"가 가장 길기 때문에 3

3. 처음 풀이 

• 왼쪽을 고정 후 오른쪽은 한칸씩 이동하며 새로운 문자가 등장하면 현재 문자열을 temp에 저장
• 이미 나온 문자가 등장하면 왼쪽을 한칸 이동하고 temp를 비운 후 반복
• temp를 비울 때 마다 이전까지 구한 최댓값 result와 현재 문자열 길이 중 최댓값으로 result 업데이트
• 매번 문자열 temp에 문자가 있는 지 확인해야하므로 속도 개선 필요
• 이렇게 두 포인터가 움직일 때 기존 내용을 딕셔너리에 저장하면 속도를 개선할 수 있음

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        result = 0 #길이의 최댓값 업데이트 
        temp = '' #현재 부분 문자열을 보관
        i = 0 #출발 index = 0
        while i <len(s): #문자열 끝까지 갈때까지 반복
            a=s[i] #i번째 문자가
            if a not in temp: #처음 나왔다면
                temp += a #temp에 문자를 저장하고
                i += 1 #다음 칸으로 i 이동
            else: #i번째 문자가 이미 나온 문자라면
                result = max(result, len(temp)) #이전의 문자열과 현재 문자열 길이 중 큰 것으로 업데이트
                i -= len(temp)-1 #출발 index를 현재 문자열 시작점 한칸 오른쪽으로 이동
                temp = '' #다음 문자열 보관하기 위해 리셋
        result = max(result, len(temp)) #
        return result

4. 개선된 풀이 

• 오른쪽 포인터 r이 한칸씩 오른쪽으로 이동하며 등장하는 문자와 인덱스를 딕셔너리에 저장
• 이때 새로운 문자가 등장하면 length 값과 현재 두 포인터 사이 길이(r-l+1)의 max값으로 lengh를 업데이트
• 이미 나온 문자가 등장하면 왼쪽 시작점을 마지막으로 나온 문자 다음으로 옮김

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        seen = {}
        l = 0
        length = 0
        for r in range(len(s)):
            char = s[r]
            if char in seen and seen[char] >= l:
                l = seen[char] + 1
            else:
                length = max(length, r - l + 1)
            seen[char] = r

        return length

5. 배운 점 

• 투 포인터, 슬라이딩 윈도우 방법을 이용하면 시간복잡도 O(n²)을 O(n)로 줄일 수 있음 
• 이때 이미 관찰한 내용을 딕셔너리에 저장함