[LeetCode] Longest Substring Without Repeating Characters | 투포인터 | 파이썬 알고리즘 인터뷰, 정답, 소스코드

박상길, 『파이썬 알고리즘 인터뷰』를 정리한 내용입니다.

https://leetcode.com/problems/longest-substring-without-repeating-characters/

Longest Substring Without Repeating Characters - LeetCode

---

문제 요약

• 문자열이 주어질 때 중복문자가 없는 가장 긴 부분문자열의 길이를 구하라

---

문제 조건

• 0 <= len(s) <= 50,000
• s는 영어, 숫자, 공백으로 구성
• 대소문자 구분해야함

---

핵심 알고리즘

• 투포인터 사용. left = 0, right = 1로 초기화. right < len(s)인동안
• s[left:right]에 사용된 문자를 딕셔너리에 저장
• 만약 s[left:right]에 s[right]에 해당하는 문자가 있으면
  s[left:right]에서 s[right]가 없어질때까지 left +=1
• 만약 s[left:right]에 s[right]에 해당하는 문자가 없으면 right +=1
• 주어진 문자의 길이가 0이면 0 반환, 1이면 1 반환

---

소스코드

import collections

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        answer = 0
        left, right = 0, 1

        if s == "":
            return 0
        if len(s) == 1:
            return 1

        used = collections.defaultdict(int)
        used[s[left]] += 1

        while right < len(s):

            while used[s[right]] > 0:
                used[s[left]] -= 1
                left += 1

            used[s[right]] += 1
            right += 1
            answer = max(answer, right - left)

        return answer