題目網址：https://leetcode.cn/problems/longest-substring-without-repeating-characters/

題意：給一 string s, 返回一沒有重複 char 的最長 substring 的長度。

Solution：

想法：利用 Sliding Window, 類似 424. Longest Repeating Character Replacement, 每次檢查 s[right] 是否已經在 visited 中

  • 若是, 則移除 s[left], 且 left + 1, 直到 visited 中不存在 s[right]
  • 將 s[right] 加入到 visited 中
  • 更新 res
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int left = 0, res = 0;
        unordered_set<char> visited;

        for (int right = 0; right < s.size(); ++right) {
            while (visited.find(s[right]) != visited.end()) {
                visited.erase(s[left]);
                ++left;
            }
            visited.emplace(s[right]);
            res = max(res, right - left + 1);
        }

        return res;
    }
};
  • time：$O(n)$ ➔ s 中的每個元素最多被拜訪 2 次（left, right）
  • space：$O(1)$ ➔ cnt 長度最多為 26, 故只需常數空間