3. Longest Substring Without Repeating Characters

[fockspaces]

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.

Constraints:

0 <= s.length <= 5 * 104 s consists of English letters, digits, symbols and spaces.

[fockspaces]

我用 queue 作為 window，set 紀錄目前 queue 有的值，當新字母跟 set 內元素重複，不斷縮減 queue 直到不重複為止

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_set<char> set;
        queue<char> q;
        int ans = 0;
        for(char c : s) {
            while(q.size() && set.count(c)) {
                char pop = q.front(); q.pop();
                set.erase(pop);
            }
            set.insert(c); q.push(c);
            int size = q.size();
            ans = max(ans, size);
        }
        return ans;
    }
};

[fockspaces]

也可以直接用 two-pointers 實作 sliding window，一樣用 set 來紀錄 window 內元素

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_set<char> set;
        queue<char> q;
        int ans = 0;
        for(char c : s) {
            while(q.size() && set.count(c)) {
                char pop = q.front(); q.pop();
                set.erase(pop);
            }
            set.insert(c); q.push(c);
            int size = q.size();
            ans = max(ans, size);
        }
        return ans;
    }
};

[fockspaces]

補上 python 版本，要特別熟悉 set 用法

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        box, start, ans = set(), 0, 0
        for i, word in enumerate(s):
            while start < i and word in box:
                _, start = box.remove(s[start]), start + 1
            box.add(word)
            ans = max(ans, len(box))
        return ans

[fockspaces]

sliding window + set

keep tracking the char in the window, then once the current char is duplaicated with set, moving the pointer forward, until there's no duplicated char in the set.

be sure to update the max_len for the final answer

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        pt = 0
        max_len = 0
        char_set = set()
        for i in range(len(s)):
            while pt < i and s[i] in char_set:
                char_set.remove(s[pt])
                pt += 1
            char_set.add(s[i])
            max_len = max(max_len, i - pt + 1)
        return max_len