[ 3 ] [ Queue, set ] Longest Substring Without Repeating Characters

문제 설명

---

3.Longest Substring Without Repeating Characters

Medium

Given a strings, 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

Constraints:

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

---

풀이 과정

1. 현재 중복을 검사할 set과 Substring을 담을 queue를 구성한다.
2. 문자열을 왼쪽에서부터 오른쪽으로 문자 하나씩 진행한다
   • 문자 하나씩 반복문을 진행한다.
   • 만약 문자가 set 안에 있는 경우는, 기존 길이가 answer보다 길다면 저장한 다음, 해당 문자까지 queue와 set에서 빼주고 set하고 queue의 맨 마지막에 해당 문자를 다시 넣어준다.
   • 만약 문자가 set 안에 있지 않은 경우는 그대로 queue와 set에 넣어주면 된다.
3. 길이 최댓값을 리턴

---

소스 코드

---

from collections import deque

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        answer = 0
        length = 1
        if len(s) == 0:
            return 0
        check = set([s[0]])
        queue = deque([s[0]])
        for i in range(1, len(s)):
            if s[i] not in check:
                length += 1
                check.add(s[i])
                queue.append(s[i])
            else:
                answer = max(length, answer)
                while queue:
                    p = queue.popleft()
                    check.remove(p)
                    if p == s[i]:
                        break
                queue.append(s[i])
                check.add(s[i])
                length = len(check)

        answer = max(length, answer)
        return answer