牛客235698题最长子串解题思路与代码解析（滑动窗口+哈希表优化）
24小时前
一、题目解读
牛客235698题要求求解一个字符串中最长子串的长度，该子串需满足仅包含两种不同的字符。例如，输入字符串“abccde”，输出应为“bcc”或“cde”等，长度均为3。题目核心在于高效判断子串的字符种类限制，需通过算法设计在O(n)时间内完成。
二、解题思路
1. 滑动窗口：通过左右指针动态维护子串范围，右指针不断向右扩展，左指针根据条件移动收缩。
2. 哈希表：使用unordered_map记录窗口内字符出现次数，实时统计不同字符种类数。
3. 关键逻辑：当字符种类超过2时，左指针向右移动，删除冗余字符（通过哈希表计数判断），确保窗口始终满足条件，并更新最长长度。
三、解题步骤
1. 初始化：创建哈希表charCount，左指针left=0，最大长度maxLen=0。
2. 右指针扩展：循环遍历字符串，每次将s[right]字符计数+1，扩展窗口。
3. 左指针收缩：若哈希表大小（字符种类）>2，则执行：
○ 减少s[left]计数，若计数为0则从哈希表中删除该键，左指针右移。
○ 循环直至字符种类≤2。
4. 更新长度：每次循环计算当前窗口长度right-left+1，与maxLen取最大值。
5. 返回结果：最终maxLen即为最长满足条件的子串长度。
四、代码和注释
#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;
int longestSubstring(string s) {
unordered_map<char, int> charCount; // 记录窗口中字符出现次数
int left = 0, maxLen = 0; // 窗口左边界和最大长度
for (int right = 0; right < s.size(); ++right) {
charCount[s[right]]++; // 扩展右边界，增加当前字符计数
// 当窗口内字符种类超过2时，移动左边界
while (charCount.size() > 2) {
charCount[s[left]]--; // 减少左边界字符计数
if (charCount[s[left]] == 0) {
charCount.erase(s[left]); // 如果计数为0，从哈希表中移除
}
left++; // 移动左边界
}
// 更新最大长度
maxLen = max(maxLen, right - left + 1);
}
return maxLen;
}
int main() {
string s;
cin >> s;
cout << longestSubstring(s) << endl;
return 0;
}五、总结
该算法巧妙结合滑动窗口与哈希表，将字符种类判断转化为计数问题，时间复杂度为O(n)，空间复杂度为O(|Σ|)（Σ为字符集大小）。适用于对字符串子串限制类问题的高效求解。通过动态调整窗口边界，避免暴力枚举，显著提升性能，是解决此类题目的典型思路。
原创内容 转载请注明出处
