无重复字符的最长子串
给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: s = “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。
示例 2:
输入: s = “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。
示例 3:
输入: s = “pwwkew”
输出: 3
解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，“pwke” 是一个子序列，不是子串。
提示：
0 <= s.length <= 5 * 104
s 由英文字母、数字、符号和空格组成
class Solution {
public:
int lengthOfLongestSubstring(string s) {
// 哈希集合，记录每个字符是否出现过
unordered_set<char> occ;
int n = s.size();
// 右指针，初始值为 -1，相当于我们在字符串的左边界的左侧，还没有开始移动
int rk = -1, ans = 0;
// 枚举左指针的位置，初始值隐性地表示为 -1
for (int i = 0; i < n; ++i) {
if (i != 0) {
// 左指针向右移动一格，移除一个字符
occ.erase(s[i - 1]);
}
while (rk + 1 < n && !occ.count(s[rk + 1])) {
// 不断地移动右指针
occ.insert(s[rk + 1]);
++rk;
}
// 第 i 到 rk 个字符是一个极长的无重复字符子串
ans = max(ans, rk - i + 1);
}
return ans;
}
};
解析：当输入一个字符串 s，要求找出其中最长的无重复字符子串的长度。这段代码是使用滑动窗口和哈希集合的方法来解决这个问题。
- 定义了一个无序哈希集合
occ用来记录每个字符是否已经出现过。 - 初始化了右指针
rk为 -1，相当于在字符串的左边界的左侧，还没有开始移动。 - 初始化了结果变量
ans为 0，用来记录最长的无重复字符子串的长度。 - 使用
for循环遍历字符串s中的每个字符，作为左指针i，从 0 到 n-1，其中 n 是字符串s的长度。 - 在循环体内，先将左指针
i后移一位，从而将字符s[i-1]从哈希集合occ中移除，表示它不再在当前考虑的子串中。 - 然后使用
while循环，将右指针rk向右移动，将字符s[rk+1]添加到哈希集合occ中，直到遇到重复的字符或者到达字符串的末尾。这样，哈希集合occ中存储的就是当前考虑的子串中的所有字符，且都是不重复的。 - 在每一步移动右指针
rk的过程中，计算并更新当前子串的长度，即rk - i + 1，并将其与结果变量ans比较，取较大值作为新的最长无重复字符子串的长度。 - 循环结束后，返回最终的结果
ans，即最长无重复字符子串的长度。
这个算法的时间复杂度为 O(n)，其中 n 是输入字符串的长度，因为每个字符最多被访问两次：一次通过左指针 i，一次通过右指针 rk。空间复杂度为 O(k)，其中 k 是字符串 s 中的不重复字符的个数，因为哈希集合 occ 存储了这些字符。这个算法的思路简洁高效，适用于解决类似的字符串处理问题。
在 C++ 中，哈希表（unordered_map、unordered_set）是一种使用哈希函数来实现的关联容器，用于存储键-值对（对于 unordered_map）或者值的集合（对于 unordered_set）。下面是对代码中使用的 erase 和 count 函数的解释：
erase 函数：在哈希表中删除指定键对应的键-值对或者值。语法如下：
unordered_map::erase(const key_type& k); // 删除键为 k 的键-值对
unordered_set::erase(const key_type& k); // 删除值为 k 的元素
erase 函数返回一个表示删除的元素数目的整数，如果找不到指定的键或者值，则返回 0。在代码中的用法是 occ.erase(s[i - 1])，即从哈希集合 occ 中删除字符 s[i - 1]。
count 函数：在哈希表中查找指定键或者值的出现次数。语法如下：
unordered_map::count(const key_type& k); // 返回键为 k 的键-值对的数目，只能为 0 或者 1
unordered_set::count(const key_type& k); // 返回值为 k 的元素的数目，只能为 0 或者 1
count 函数返回一个表示键或者值的出现次数的整数，对于哈希表来说，由于键和值是唯一的，因此其返回值只能为 0 或者 1。在代码中的用法是 !occ.count(s[rk + 1])，即判断字符 s[rk + 1] 是否在哈希集合 occ 中出现过，如果没有出现过，则执行后续的插入操作。注意这里使用了取反操作 !，因为 count 函数返回的是出现次数，而在这里我们只关心是否出现过，因此取反可以简化逻辑。
