连续出现的字符

题目描述

给定正整数 $k$ （ $1 \leqslant k \leqslant 1000$ ）和字符串 $s$ （ $1 \leqslant |s| \leqslant 2500$ ，不含空白符），输出 $s$ 中第一个连续出现至少 $k$ 次的字符；若不存在，输出 No。

输入：第一行为正整数 $k$ ，第二行为字符串 $s$ 。输出：一个字符或 No。

样例输入 $k=3$ 、 $s=$ abcccaaab 时，字符 c 连续出现 3 次，输出 c。

思路

维护当前段计数 run，逐位置扫描：每个位置先判 run == k（成立则输出当前字符），再按 $s[i]$ 与 $s[i+1]$ 是否相同决定 run+1 或归 1。这样末端段恰好在串尾凑满 $k$ 时不会再触发检查（其后无位置）， $k=1$ 时输出的是第一个与前一个相同的字符，均与标准程序行为一致。时间复杂度 $O(|s|)$ 。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-29 20:49
# update_at: 2026-09-29 20:49

import sys

NO_ANSWER = "No"  # 不存在满足条件的字符时的输出


def first_repeat_char(s: str, k: int) -> str:
    """回答：字符串中第一个"连续出现至少 k 次"的字符；没有则回答 No。

    与标准程序一致的处理顺序：位置 i 处先看前一段是否已凑满 k 个，
    再把 s[i] 并入当前段。这样末尾凑满 k 的段不会再触发（其后无元素），
    k=1 时输出第一个"与前一个相同"的字符。
    """
    run = 0
    for i, ch in enumerate(s):
        if run == k:  # 前一段已连续出现 k 次，段尾字符即答案
            return ch
        can_continue = i + 1 < len(s) and s[i + 1] == ch  # s[i] 后面还跟着同字符
        run = run + 1 if can_continue else 1              # 否则当前段从 1 重新数起
    return NO_ANSWER


def solve() -> None:
    data = iter(sys.stdin.buffer.read().split())
    k = int(next(data))          # 次数门槛 k
    s = next(data).decode()      # 待查字符串；本题按字符扫描，故解码成 str

    print(first_repeat_char(s, k))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 03:36
 * update_at: 2026-10-05 03:36
 */

#include <cstdio>
#include <cstring>

typedef long long ll;

const ll MAXL = 2600; // 字符串长度上限 2500

char s[MAXL]; // 输入字符串
ll k;         // 至少连续出现的次数

int main() {
    scanf("%lld %s", &k, s);
    ll len = strlen(s);

    ll run = 0; // 当前段计数，0 表示还没有进入任何段
    for (ll i = 0; i < len; i++) {
        if (run == k) { // 先判：前一段已连续出现 k 次，输出当前字符
            printf("%c\n", s[i]);
            return 0;
        }
        if (i + 1 < len && s[i] == s[i + 1]) // 后更：向右看一位是否同字符
            run++;
        else
            run = 1; // 段断裂（或到达串尾），重新从 1 数起
    }
    printf("No\n"); // 整串扫完都没有触发（含末端段恰好凑满 k 的情况）
    return 0;
}

目录

题目描述

思路

参考代码