3. Longest Substring Without Repeating Characters

Category	ps/다이나믹 프로그래밍
Tag	다이나믹 프로그래밍
Tags	hash mapsliding window
난이도	★★
발행 여부
사이트	Leet code
실수 유형
이해	완벽히 이해
최종 편집 일시	@2021년 12월 1일 오후 10:27
푼 날짜	@2021년 11월 30일 오후 10:57

문제 해설 및 주의사항

원문

번역 및 주의사항

풀이

내 풀이 코드 (dp)

풀이 코드 (책)

퇴고

문제 해설 및 주의사항

원문

• 열기

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

  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.
  

  Example 4:

  Input: s = ""
  Output: 0

번역 및 주의사항

---

풀이

내 풀이 코드 (dp)

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        # 빈 문자열 처리
        if not s :
            return 0
        if len(s) == 1:
            return 1
        # dp[i] : s[i] 로 끝내는 가장 긴 중복없는 부분 문자열의 최대 길이를 저장
        dp = [0 for _ in range(len(s))]
        dp[0] = 1
        
        ans = -1
        
        for i in range(1, len(s)):
            previous_same = -1
						# s[i - 1] 로 끝내는 가장 긴 중복없는 부분 문자열에서 s[i] 가 있는지 검사하고, index 를 찾아냄
            for j in range(i-1 - dp[i-1] + 1, i):
                if s[j] == s[i]:
                    previous_same = j
                    break
            # 중복되는 문자가 없으면, 이전의 길이에 1 큼
            if previous_same == -1:
                dp[i] = dp[i-1] + 1
						# 중복되는 문자가 있으면, 현재부터 중복 문자까지의 거리를 가짐
            else:
                dp[i] = i - previous_same
            if dp[i] > ans :
                ans = dp[i]
        
        return ans

풀이 코드 (책)

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        # 어떤 문자의 최신 위치를 저장한다.
        used = {}
        max_length = start = 0
        for index, char in enumerate(s):
            print(used)
            # 이미 등장했던 문자이고, 현재 문자의 바로 이전 위치가 현재 시작점보다 크다면
            if char in used and start <= used[char]:
                start = used[char] + 1
            else:  # 최대 부분 문자열 길이 갱신
                max_length = max(max_length, index - start + 1)

            # 현재 문자의 위치 삽입
            used[char] = index

        return max_length

• 월등히 빠르다.

• sliding window 가 어떻게 움직이고 어떻게 구현되었는지 잘 기억해두자.
  • start ~index 가 하나의 sliding window 로써 동작한다.

• 이미 등장했던 문자를 처리하는 과정을 잘 기억해야한다.
  • used[char] 는 현재 문자의 가장 최신의 이전 위치를 기억하므로, 그때보다 한 칸 뒤로 간 것을 start 로 설정한다.
  • 예시로, dfdw 를 생각해보자.
    • index=2 일때, char='d' 이다.
    • 'd' 의 가장 최신 위치 즉, used['d'] 는 0 이다.
    • 그러므로, start 는 1 이 된다.

• 등장 하지 않았던 문자라면, 슬라이딩 윈도우의 크기를 max_length 와 비교하여 최대 부분 문자열 길이를 갱신한다.

• start <= used[char] : 현재 위치에서 중요한 것은 오직 슬라이딩 윈도우 범위 내에서의 일이다. 만약 used[char] 의 값 즉, 현재 문자의 가장 최신 위치가 슬라이딩 윈도우 밖이라면 신경 쓸 이유가 없는 것이다.

---

퇴고