穷哈哈~

思路

拿到这题先理解"笑声"的定义：笑声是由字母 h 和 a 交替组成的序列。比如 "a"、"ha"、"aha"、"hahaha" 这些都是合法的笑声，但 "hh"、"aa"、"abc" 就不是。

那问题就变成了：在字符串里找一个最长的连续子串，这个子串只包含 h 和 a，并且相邻字符不相同。

怎么做？直接一次遍历就够了。维护一个当前合法笑声的长度 cur：

  1. 如果当前字符不是 h 也不是 a，笑声中断，cur 归零；
  2. 如果当前字符是 h 或 a，而且和前一个字符不一样（或者是新开头），cur 加一；
  3. 如果当前字符和前一个字符相同（比如连续两个 a），说明交替被打破了，cur 重置为 1（当前字符本身可以作为新笑声的开头）。

遍历过程中不断更新最大值就行了。

代码

#include <iostream>
#include <string>
using namespace std;

int main() {
    int n;
    cin >> n;
    string s;
    cin >> s;

    int ans = 0, cur = 0;
    for (int i = 0; i < n; i++) {
        if (s[i] != 'h' && s[i] != 'a') {
            cur = 0;                    // 不是h或a，笑声中断
        } else if (i == 0 || cur == 0) {
            cur = 1;                    // 新笑声开始
        } else if (s[i] != s[i - 1]) {
            cur++;                      // 交替延续
        } else {
            cur = 1;                    // 连续相同字符，重新开始
        }
        ans = max(ans, cur);
    }

    cout << ans << endl;
    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        String s = sc.next();

        int ans = 0, cur = 0;
        for (int i = 0; i < n; i++) {
            char c = s.charAt(i);
            if (c != 'h' && c != 'a') {
                cur = 0;                // 不是h或a，笑声中断
            } else if (i == 0 || cur == 0) {
                cur = 1;                // 新笑声开始
            } else if (c != s.charAt(i - 1)) {
                cur++;                  // 交替延续
            } else {
                cur = 1;                // 连续相同字符，重新开始
            }
            ans = Math.max(ans, cur);
        }

        System.out.println(ans);
    }
}

n = int(input())
s = input()
ans = 0
cur = 0
for i in range(n):
    if s[i] not in ('h', 'a'):
        cur = 0
    elif i == 0 or cur == 0:
        cur = 1
    elif s[i] != s[i - 1]:
        cur += 1
    else:
        cur = 1
    ans = max(ans, cur)
print(ans)

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
const lines = [];
rl.on('line', line => lines.push(line));
rl.on('close', () => {
    const n = parseInt(lines[0]);
    const s = lines[1];
    let ans = 0, cur = 0;
    for (let i = 0; i < n; i++) {
        if (s[i] !== 'h' && s[i] !== 'a') {
            cur = 0;
        } else if (i === 0 || cur === 0) {
            cur = 1;
        } else if (s[i] !== s[i - 1]) {
            cur++;
        } else {
            cur = 1;
        }
        ans = Math.max(ans, cur);
    }
    console.log(ans);
});

复杂度分析

  • 时间复杂度: ，一次遍历搞定。
  • 空间复杂度: ，只用了两个额外变量。

小结

这题本质就是一个滑动窗口/双指针的简化版——找最长的满足条件的连续子串。条件有两个：字符只能是 h 或 a，而且相邻不能重复。一次遍历维护当前长度就完事了，没什么花哨的。看到"最长连续子串"这类关键词，第一反应就是线性扫描 + 维护状态，基本上都能一遍过。