当前位置:首页 > 牛客题解 > 寻找最长交替序列:牛客230507题深度解析

寻找最长交替序列:牛客230507题深度解析

3周前 (06-21)牛客题解68

截图未命名.jpg 寻找最长交替序列:牛客230507题深度解析 字符串模式匹配 交替序列 滑动窗口算法 牛客网算法题 动态重置机制 牛客网230507 第1张

问题理解与算法设计

这道题目要求我们在给定字符串中找出最长的符合特定模式的子串。小哈的笑声由'a'和'h'交替组成,可以是"a"和"h"的任意交替组合,但不能出现其他字母或连续相同的字母交替(如"aaaa"不合法)。

关键观察点:

  1. 合法序列只能包含'a'和'h'两种字符

  2. 字符必须严格交替出现(不能有连续相同的字符)

  3. 需要找出所有可能交替模式中的最长序列

完整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.核心思路:

  1. 枚举所有可能的交替模式:共有两种有效模式:"ahah..."和"haha..."

  2. 滑动窗口技术:对每种模式,使用类似滑动窗口的方法扫描字符串

  3. 动态重置机制:当遇到不符合预期的字符时,重置计数器但回退一步重新检查

2.复杂度分析:

  • 时间复杂度:O(n),虽然有双重循环,但内层循环实际上只遍历字符串两次

  • 空间复杂度:O(1),仅使用了常数级别的额外空间

新手学习指南

  1. 理解交替模式:先手工分析几个示例,如"ahahah"和"hahaha"的区别

  2. 模式枚举思想:学习如何系统地枚举所有可能的合法模式

  3. 滑动窗口技巧:这是字符串处理中的常见技术,值得重点掌握

  4. 边界条件处理:特别注意字符串开头和结尾的特殊情况

常见错误与调试技巧

  1. 忘记重置计数器:会导致错误累加长度

  2. 模式枚举不全:漏掉"ah"或"ha"其中一种模式

  3. 边界条件处理不当:特别是字符串开头和单字符情况

  4. 回退逻辑错误:可能导致无限循环或漏掉有效序列


原创内容 转载请注明出处

分享给朋友:

发表评论

访客

看不清,换一张

◎欢迎参与讨论,请在这里发表您的看法和观点。