Longest Substring Without Repeating Characters

LeetCode 3. Longest Substring Without Repeating Characters

원문

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

풀이

Minimum Size Subarray Sum 문제를 참고했다.

1. 문자를 저장하기 위한 큐 letters와 세트 chk, 길이를 저장하기 위한 변수 result를 선언한다.
2. s를 순회한다.
   1. s[i]가 chk에 없는 경우
      1. letters의 뒤에 s[i]를 추가한다.
      2. chk에 s[i]를 추가한다.
   2. s[i]가 chk에 있는 경우
      1. letters의 가장 앞 원소가 s[i]가 될 때까지 letters의 앞에서 문자를 제거하고 그 문자를 chk에서도 제거한다.
      2. letters의 가장 앞 원소가 s[i]가 되었다면 letters의 앞에서 그 문자를 제거하고 letters의 뒤에 추가한다.
   3. result의 값을 result와 letters의 길이 중 긴 것으로 갱신한다.
3. result를 반환한다.

코드

Python

from collections import deque


class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        letters, chk = deque(), set()
        result = 0

        for i in range(len(s)):
            if s[i] not in chk:
                letters.append(s[i])
                chk.add(s[i])
            else:
                while letters[0] != s[i]:
                    chk.remove(letters.popleft())
                letters.popleft()
                letters.append(s[i])
            result = max(result, len(letters))

        return result

Java

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Deque<Character> que = new ArrayDeque<>();
        Set<Character> letters = new HashSet<>();
        int result = 0;
        int idx = 0;

        while (idx < s.length()) {
            if (letters.contains(s.charAt(idx))) {
                while (que.peekFirst() != s.charAt(idx)) {
                    letters.remove(que.pollFirst());
                }
                que.pollFirst();
                que.add(s.charAt(idx));
                idx++;
            } else {
                que.add(s.charAt(idx));
                letters.add(s.charAt(idx));
                idx++;
            }
            result = Math.max(result, que.size());
        }
        return result;
    }
}