牛客230507题解析：交替字符序列的动态规划解法
3天前
一、题目解读
牛客230507题要求从给定字符串中寻找交替出现的字符序列（如“haha”或“ahaha”）的最长长度。题目关键在于识别字符交替模式，并计算其最大连续次数。例如，在字符串“ahahahaha”中，最长的交替序列为“ahahaha”（长度6）。此问题需高效遍历所有可能的交替组合，并处理字符不匹配时的逻辑。
二、解题思路
采用动态规划+回退策略解决该问题。核心思想是通过两层循环枚举所有可能的交替模式（如“a-h”或“h-a”），然后遍历字符串验证每个字符是否符合当前模式。当遇到不匹配字符时，通过回退机制重新检查，避免遗漏潜在的长序列。该算法巧妙利用交替模式的对称性，减少无效计算，同时保证正确性。
三、解题步骤
1. 初始化变量：定义max_len记录最长序列，n为字符串长度。
2. 枚举交替模式：使用两层循环遍历首字符first和次字符second（如“a”和“h”），跳过相同字符的组合（如“a-a”）。
3. 动态匹配字符：
○ 初始化当前序列长度current_len和期望字符expected（首字符）。
○ 遍历字符串，若当前字符匹配期望，则更新长度并切换期望字符（如“a”→“h”或“h”→“a”）。
○ 若不匹配，则重置长度和期望，并回退一步重新检查（关键步骤，避免跳过可能的序列）。
4. 更新最大长度：每次循环结束后比较current_len与max_len，取最大值。
5. 返回结果：最终输出max_len。
四、代码与注释
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int findMaxLaugh(string s) {
int max_len = 0; // 记录最长交替序列长度
int n = s.length();
// 检查所有可能的交替模式（如"a-h"或"h-a"）
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++; // 匹配时长度+1
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;
}五、总结
该解法通过枚举交替模式结合动态回退，有效解决了字符序列的最长交替查找问题。时间复杂度为O(n²)，虽未达最优，但逻辑清晰且易于理解。优化方向可考虑状态压缩或滑动窗口技术进一步降低时间复杂度。此思路对处理类似交替模式问题具有参考价值。
原创内容 转载请注明出处
