寻找最长交替序列:牛客230507题深度解析
问题理解与算法设计
这道题目要求我们在给定字符串中找出最长的符合特定模式的子串。小哈的笑声由'a'和'h'交替组成,可以是"a"和"h"的任意交替组合,但不能出现其他字母或连续相同的字母交替(如"aaaa"不合法)。
关键观察点:
合法序列只能包含'a'和'h'两种字符
字符必须严格交替出现(不能有连续相同的字符)
需要找出所有可能交替模式中的最长序列
完整C++代码实现
#include <iostream> #include <string> #include <algorithm> using namespACe std; int findMaxLaugh(string s) { int max_len = 0; int n = s.length(); // 检查所有可能的交替模式 for (char first : {'a', 'h'}) { for (char second : {'a', 'h'}) { if (first == second) continue; // 跳过相同字符的无效模式 int current_len = 0; char expected = first; // 当前期望的字符 for (int i = 0; i < n; ++i) { if (s[i] == expected) { current_len++; expected = (expected == first) ? second : first; // 切换期望字符 max_len = max(max_len, current_len); } else { current_len = 0; expected = first; // 重置期望字符 // 回退一步重新检查,避免漏掉可能的序列 if (s[i] == first) i--; } } } } return max_len; } int main() { int N; string S; cin >> N >> S; cout << findMaxLaugh(S) << endl; return 0; }
算法详解与优化
1.核心思路:
枚举所有可能的交替模式:共有两种有效模式:"ahah..."和"haha..."
滑动窗口技术:对每种模式,使用类似滑动窗口的方法扫描字符串
动态重置机制:当遇到不符合预期的字符时,重置计数器但回退一步重新检查
2.复杂度分析:
时间复杂度:O(n),虽然有双重循环,但内层循环实际上只遍历字符串两次
空间复杂度:O(1),仅使用了常数级别的额外空间
新手学习指南
理解交替模式:先手工分析几个示例,如"ahahah"和"hahaha"的区别
模式枚举思想:学习如何系统地枚举所有可能的合法模式
滑动窗口技巧:这是字符串处理中的常见技术,值得重点掌握
边界条件处理:特别注意字符串开头和结尾的特殊情况
常见错误与调试技巧
忘记重置计数器:会导致错误累加长度
模式枚举不全:漏掉"ah"或"ha"其中一种模式
边界条件处理不当:特别是字符串开头和单字符情况
回退逻辑错误:可能导致无限循环或漏掉有效序列
原创内容 转载请注明出处