题解 | #牛群的独特排列# 集合、移动窗口

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param s string字符串
     * @return int整型
     */
    int lengthOfLongestSubstring(string s) {
        int n = s.size();
        int ans = 0;
        int l = 0, r = 0;
        unordered_set<int> st;
        while (r < n && l <= r) {
            // 向右遍历，当新元素一直未在st中出现时，st插入新元素，同时右移
            while (st.find(s[r]) == st.end() && r < n) {
                st.insert(s[r]);
                r++;
            }
            // 找到了一个重复元素，更新此时的最长长度，同时在st中删去l并使l左移
            ans = max(ans, (int)st.size());
            st.erase(l);
            l++;
        }
        return ans;
    }
};

时间复杂度：O(n)，数组中的每个字符最多只遍历两次，即 l 指针一次， r 指针一次

空间复杂度：O(n)，用于 st 集合，最坏情况下大小等于 n