用滑动窗口高效解决「最长无重复子串」问题

业务常见场景

• 聊天记录/输入框中，限制不能出现重复字母，需要高效检测或高亮最长无重复字符的区间。
• 游戏开发中，判断一串操作指令（如 WASD 按键序列）里，最长的不重复输入序列。
• 复杂字符串数据解析，比如玩家昵称校验、物品唯一标识生成时，检测是否有重复字符。

问题定义

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

举例：

输入: s = “abcabcbb”
输出: 3
解释: 最长子串是 “abc”，长度为 3。

暴力解法：穷举一切可能（不推荐）

• 时间复杂度：O(n²)
• 空间复杂度：O(n)

滑动窗口解法：

滑动窗口本质是用两个指针维护一个动态区间，并实时记录满足条件的区间长度。

思路流程图

1. 用哈希表（Dictionary<char, int>）存储每个字符最后出现的位置。
2. 用 left 和 right 两个指针表示窗口的左右边界。
3. 如果遇到重复字符，左指针直接跳到重复字符的下一个位置，保证区间没有重复。
4. 每次移动右指针，都更新当前最大长度。

复杂度分析

• 时间复杂度：O(n)
• 空间复杂度：O(min(n, charset_size))

核心代码

//暴力
public int LengthOfLongestSubstring(string s) {
    int maxLen = 0;
    for (int i = 0; i < s.Length; i++) {
        var set = new HashSet<char>();
        int j = i;
        while (j < s.Length && !set.Contains(s[j])) {
            set.Add(s[j]);
            j++;
        }
        maxLen = Math.Max(maxLen, j - i);
    }
    return maxLen;
}

//滑动窗口
public int LengthOfLongestSubstring(string s)
{
    var dict = new Dictionary<char, int>();
    int maxLen = 0, left = 0;
    for (int right = 0; right < s.Length; right++)
    {
        char c = s[right];
        if (dict.ContainsKey(c))
        {
            // 注意：left 只能右移，不能后退
            left = Math.Max(dict[c] + 1, left);
        }
        dict[c] = right;
        maxLen = Math.Max(maxLen, right - left + 1);
    }
    return maxLen;
}


/*

- 支持 Unicode 字符（如 Emoji）时，需要注意 `char` 可能不够用，需用 `rune`（.NET 6+）。
- 最长包含最多 K 种字符的子串？
   ——这是典型“变体问题”，只需把哈希表按字符种类数控制即可。
- 能不能只用数组？
   ——如果字符串只包含 ASCII，可以直接用 `int[128]` 当哈希表，提高效率。

*/