Leetcode一百题——无重复字符的最长子串

给定一个字符串 s ，请你找出其中不含有重复字符的 最长的长度。

示例 1:

输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。注意 "bca" 和 "cab" 也是正确答案。

示例 2:

输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:

输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

提示：

• 0 <= s.length <= 5 * 104
• s 由英文字母、数字、符号和空格组成

这个也是滑动窗口加快慢指针解出来的。

1. 算法核心思想：带频率监控的滑动窗口

该算法采用滑动窗口模型扫描整个字符串。与常规的直接跨越边界不同，此解法通过一个独立的 len 变量精确追踪当前有效窗口的长度，并使用 unordered_map 严格监控窗口内每个字符的出现频率。

• 状态 A（无冲突扩张）：当即将进入窗口的右侧字符不存在于哈希表中时，窗口安全向右扩张，同时增加长度记录。
• 状态 B（冲突逐级收缩）：当发现右侧字符已存在于哈希表中时，右边界暂停移动。左边界开始逐个向右收缩，并在哈希表中同步扣减移出字符的频率，直到触发冲突的重复字符被完全移出窗口。

class 无意义最长子串 {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_map<char, int> map;
        int len = 0;
        int maxLen = 0;

        int front = 0;
        int back = 0;

        while (back < s.size()) {
            char c = s[back];
            if (map.find(c) == map.end()) {
                map[c]++;
                back++;
                len++;
            }
            else {
                map[s[front]]--;
                if (map[s[front]] == 0) {
                    map.erase(s[front]);
                }
                len--;
                front++;
            }

            if (len > maxLen) {
                maxLen = len;
            }
        }

        return maxLen;
    }
};

2. 复杂度剖析

• 时间复杂度：O(N)。虽然代码中有分支嵌套，但在最坏的情况下，字符串中的每个字符也最多只会被右指针进入一次，被左指针移出一次。哈希表的增删改查均摊耗时都是常数级，整体运行效率保持着完美的线性节奏。
• 空间复杂度：O(Σ)。这里的 Σ 代表字符集的总数。哈希表的体积被严格限制在当前窗口的不重复字符数量内。对于常规的 ASCII 字符，最多只占用 128 个常数级别的额外空间。