题解 | #穷哈哈~#

题目链接

穷哈哈~

题目描述

小哈的笑声很有特点，是由字母 'a' 和 'h' 交替组成的序列。例如 aha 和 hahah 都是合法的笑声，但 aa 和 ahha 不是。

给定一个只包含小写字母的字符串，代表小哈说的话，请你找出其中最长的、符合笑声规则的子串的长度。

解题思路

这道题要求我们找到一个字符串中由 'a' 和 'h' 交替出现的最长子串的长度。

我们可以通过一次线性扫描（one-pass）来解决这个问题。具体思路如下：

我们维护两个变量：
- max_len：用来记录到目前为止发现的最长笑声的长度。
- current_len：用来记录当前正在检查的连续笑声的长度。
我们从头到尾遍历输入的字符串。对于每个字符，我们进行判断：
- 如果字符不是 'a' 或 'h'：那么任何进行中的笑声序列到这里就中断了。我们将 current_len 重置为 0。
- 如果字符是 'a' 或 'h'：
  - 这是我们遇到的第一个 'a' 或 'h'（即 current_len 为 0），或者字符串的第一个字符就是 'a'/'h'：我们开始一个新的笑声序列，所以 current_len 置为 1。
  - 如果当前字符与前一个字符不同（例如，'a' 后面是 'h'，或 'h' 后面是 'a'）：说明笑声序列在延续。我们将 current_len 加 1。
  - 如果当前字符与前一个字符相同（例如，'a' 后面还是 'a'）：那么交替模式被打破。旧的笑声序列在此中断，同时一个新的、长度为 1 的笑声序列从当前这个字符开始。所以我们将 current_len 重新置为 1。
在遍历的每一步，当 current_len 更新后，我们都用它来更新 max_len（即 max_len = max(max_len, current_len)），以确保 max_len 始终保存着我们所见过的最大值。
遍历结束后，max_len 的值就是最终的答案。

代码

c++
java
python

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

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

    if (n == 0) {
        cout << 0 << '\n';
        return 0;
    }

    int max_len = 0;
    int current_len = 0;

    for (int i = 0; i < n; ++i) {
        if (s[i] == 'a' || s[i] == 'h') {
            // 如果是第一个字符，或者前一个字符不是'a'/'h'，或者和前一个字符相同
            if (i == 0 || (s[i-1] != 'a' && s[i-1] != 'h') || s[i] == s[i-1]) {
                current_len = 1;
            } else {
                // 和前一个字符不同，序列延续
                current_len++;
            }
        } else {
            // 序列中断
            current_len = 0;
        }
        max_len = max(max_len, current_len);
    }

    cout << max_len << '\n';

    return 0;
}

import java.util.Scanner;
import java.lang.Math;

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

        if (n == 0) {
            System.out.println(0);
            return;
        }

        int maxLen = 0;
        int currentLen = 0;
        
        for (int i = 0; i < n; i++) {
            char currentChar = s.charAt(i);
            if (currentChar == 'a' || currentChar == 'h') {
                if (i > 0 && (s.charAt(i-1) == 'a' || s.charAt(i-1) == 'h') && currentChar != s.charAt(i-1)) {
                    // 和前一个'a'/'h'字符不同，序列延续
                    currentLen++;
                } else {
                    // 序列中断或开始
                    currentLen = 1;
                }
            } else {
                // 遇到非'a'/'h'字符，序列中断
                currentLen = 0;
            }
            maxLen = Math.max(maxLen, currentLen);
        }
        System.out.println(maxLen);
    }
}

# 读取输入
n = int(input())
s = input()

if n == 0:
    print(0)
else:
    max_len = 0
    current_len = 0
    for i in range(n):
        # 如果当前字符是 'a' 或 'h'
        if s[i] in ('a', 'h'):
            # 如果是第一个字符，或者当前字符与前一个字符不同
            if i > 0 and s[i] != s[i-1] and s[i-1] in ('a', 'h'):
                current_len += 1
            else:
                # 否则，交替序列中断，重新开始计数
                current_len = 1
        else:
            # 如果当前字符不是 'a' 或 'h'，则序列中断
            current_len = 0
        
        # 更新最大长度
        max_len = max(max_len, current_len)

    print(max_len)

算法及复杂度

算法：单次遍历（线性扫描）。
时间复杂度：我们只需要对长度为 $n$ 的字符串进行一次完整的遍历，所以时间复杂度是 $O(n)$ 。
空间复杂度：我们只使用了几个额外的变量来存储当前长度和最大长度，与输入规模无关，所以空间复杂度是 $O(1)$ 。