当前位置：首页 > 牛客 > 牛客230507题解析：交替字符序列的动态规划解法

牛客230507题解析：交替字符序列的动态规划解法

4个月前 (08-20)

一、题目解读

牛客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;
}