题意概括

给定一个字符串 s，找到该字符串中不包含重复字符的 最长子串 的长度。子串是字符串中连续的一部分。

数据范围:

• 字符串 s 的长度满足 $0 \le \text{length}(s) \le 5 \times 10^4$。
• s 由英文字母、数字、符号和空格组成。

基础知识

滑动窗口 (Sliding Window)

这个问题是使用“滑动窗口”算法的经典范例。滑动窗口可以看作是一个由两个指针（左指针 l 和右指针 r）界定的动态区间。这个窗口在字符串上滑动，根据特定条件进行扩展或收缩，以寻找满足条件的解。

1. 窗口定义: 我们定义一个窗口 [l, r]，表示当前正在考察的子串。我们的目标是维护这个窗口内的所有字符都是唯一的。

2. 算法流程:

   • 初始化左指针 l = 0，右指针 r = 0，最大长度 ans = 0。
   • 使用一个哈希表或数组（例如 cnt[128]，对应 ASCII 码）来记录窗口内每个字符出现的次数。
   • 不断向右移动右指针 r 来扩展窗口：
     • 将新字符 s[r] 加入窗口，并将其在 cnt 数组中对应的计数加一。
     • 检查 s[r] 在窗口内的计数是否大于 1。
     • 如果大于 1，说明窗口内出现了重复字符。此时，我们需要收缩窗口。
     • 不断向右移动左指针 l，并将离开窗口的字符 s[l] 的计数减一，直到 s[r] 的计数变回 1 为止。这表示窗口内的重复字符已被移除。
   • 在每次扩展窗口（并可能伴随收缩）之后，窗口 [l, r] 内的子串都是不含重复字符的。我们用当前窗口的长度 r - l + 1 来更新最大长度 ans。
   • 重复此过程，直到右指针 r 到达字符串的末尾。

复杂度分析:

• 时间复杂度: $O(N)$，其中 $N$ 是字符串的长度。虽然有两层循环，但每个字符最多被左指针和右指针各访问一次，所以总操作数是线性的。
• 空间复杂度: $O(K)$，其中 $K$ 是字符集的大小（对于 ASCII 是 128）。这是一个常数空间，所以空间复杂度为 $O(1)$。

样例

样例 1

• 输入: abcabcbb
• 输出: 3
• 说明: 最长无重复字符子串是 "abc"。

样例 2

• 输入: bbbbb
• 输出: 1
• 说明: 最长无重复字符子串是 "b"。

样例 3

• 输入: pwwkew
• 输出: 3
• 说明: 最长无重复字符子串是 "wke"。

C++ 代码实现

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    string s;
    cin >> s;

    if (s.empty()) {
        cout << 0 << endl;
        return 0;
    }

    int n = s.length();
    int cnt[128] = {0}; // 假设为 ASCII 字符集
    int ans = 0;
    int l = 0; // 滑动窗口左边界

    for (int r = 0; r < n; r++) {
        // 右指针 r 扩展窗口，新字符 s[r] 进入窗口
        cnt[s[r]]++;

        // 如果 s[r] 出现次数大于 1，说明窗口内有重复
        // 需要收缩左边界 l，直到 s[r] 的次数变回 1
        while (cnt[s[r]] > 1) {
            cnt[s[l]]--;
            l++;
        }

        // 此时 [l, r] 窗口内没有重复字符
        // 更新最大长度
        ans = max(ans, r - l + 1);
    }

    cout << ans << endl;

    return 0;
}