[알고리즘][해시 테이블] - 3. 중복 문자 없는 가장 긴 부분 문자열

 

📖이 포스팅은 '파이썬 알고리즘 인터뷰 - 박상길님' 책을 보고 작성되었습니다.

---

😎문제 : https://leetcode.com/problems/longest-substring-without-repeating-characters/submissions/

중복 문자가 없는 가장 긴 부분 문자열의 길이를 리턴하라

---

[슬라이딩 윈도우와 투 포인터로 사이즈 조절]

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        used ={}
        max_length = start = 0
        for i, char in enumerate(s):
            #이미 등장한 문자라면 start 갱신
            if char in used and start <= used[char]:
                start = used[char] +1
            else:
                max_length =max(max_length, i - start +1)
            # 현재 문자의 위치 삽입
            used[char] = i
            
        return max_length

• 이때 정답은 부분 문자열이어야 한다. 서브시퀀스는 연속적이지 않은 문자열로 정답인정이 되지 않느다.
• 슬라이딩 윈도우란?
  • 고정 사이즈의 윈도우가 이동하며 윈도우 내에 있는 데이터를 이용해 문제를 풀이하는 알고리즘을 말한다.