AcWing 771. 字符串中最长的连续出现的字符    原题链接    中等

作者： 作者的头像   P云 ,  2020-02-18 06:54:25 ,  所有人可见 ,  阅读 8472

78


61

题目描述

求一个字符串中最长的连续出现的字符，输出该字符及其出现次数，字符串中无空白字符（空格、回车和tab），如果这样的字符不止一个，则输出第一个。

输入格式

第一行输入整数N，表示测试数据的组数。

每组数据占一行，包含一个不含空白字符的字符串，字符串长度不超过200。

输出格式

共一行，输出最长的连续出现的字符及其出现次数，中间用空格隔开。

输入样例：

2
aaaaabbbbbcccccccdddddddddd
abcdefghigk

输出样例：

d 10
a 1

算法

(双指针) $O(n \times T)$

使用双指针扫描每一个test case，并记录下最大长度与该长度下的字符即可。

时间复杂度

每个test case的字符串会被扫描一次，总共T个test case，所以总复杂度为$O(n \times T)$。

C++ 代码

#include <iostream>
using namespace std;
int main()
{
    int T;
    cin >> T;
    while(T --)
    {
        int maxn = -1;//maxn记录最大长度
        string str, maxs;//maxs记录最大长度时的字符
        cin >> str;
        for(int i = 0; i < str.size(); i ++)
        {
            int j = i;
            int cnt = 0;
            while(str[j] == str[i] && j < str.size())//当指针j没有越界且与指针i的内容相同时移动
                j ++, cnt ++;
            if(cnt > maxn)//更新最大值
                maxn = cnt, maxs = str[i];
            i = j - 1;//移动指针i
        }
        cout << maxs << " " << maxn << endl;
    }
}

15 评论

用户头像
面向AI编程   2022-06-03 11:33      3    踩      回复

有没有大佬知道i = j - 1(移动指针是什么操作)

用户头像
642960179   2022-06-06 07:47      6    踩      回复

应该是如果直接等于j的话，第二个字符就不是从第一次出现开始了，aaaabbbb如果不-1 for循环外面会+1 数b出现个数的时候会少掉1个

用户头像
面向AI编程   2022-06-06 19:09    回复了 642960179 的评论      1    踩      回复

懂了，谢谢

用户头像
ac启动   5个月前         踩      回复

j = i + 1也能过

用户头像
玉谦平   5个月前         踩      回复

我觉得没用，删了一样过

用户头像
玉谦平   5个月前    回复了 玉谦平 的评论         踩      回复

应该主要就是为了减少计算

用户头像
略阿ting   12个月前      2    踩      回复

为啥把cin>>a写成getline(cin,a)输出就有问题啊

用户头像
单纯的忘记   7个月前      2    踩      回复

我也遇到过，不知道

用户头像
ljx031024   1个月前    回复了 单纯的忘记 的评论         踩      回复

我也想知道为什么

用户头像
付东   1个月前    回复了 ljx031024 的评论         踩      回复

getline会接收到前面的换行符，然后就是一个空串

用户头像
lfm   2023-11-24 19:09      2    踩      回复 
include <iostream>
using namespace std;
int main()
{
    int T;
    cin >> T;
    while(T –) {
    int maxn = -1;//maxn记录最大长度
    string str, maxs;//maxs记录最大长度时的字符
    cin >> str;
    for(int i = 0; i < str.size(); ){
        int j = i;
        int cnt = 0;
        while(str[j] == str[i] && j < str.size())//当指针j没有越界且与指针i的内容相同时移动
            j , cnt ;
            if(cnt > maxn)//更新最大值
                maxn = cnt, maxs = str[i];
            i = j ;//移动指针i
        }
        cout << maxs << ” ” << maxn << endl;
       }
}

将j = i - 1 修改为 j = i
for循环里的i++省略

用户头像
Sakura_84   2023-08-23 17:00      2    踩      回复 
#include<iostream>
using namespace std;
int main()
{
    int m;
    cin >> m;
    while(m --)
    {
        string s;
        cin >> s;
        int a = 0, max = 1, n;
        for(int i = 0; i < s.size(); i ++)
        {
            n = 1;
            if(s[i] == s[i + 1])
            {
                while(s[i + n] == s[i])
                    n++;
                if(n > max)
                {
                    max = n;
                    a = i;
                }
            }
        }
        cout << s[a] << " " << max << endl;
    }
    return 0;
}
用户头像
flong   2023-04-05 08:50      2    踩      回复

Q:如果没有连续的数，是不是会发生i = 0，i = j = 0， i = j - 1， i++导致死循环呢？
A:不会，因为即使不连续也会满足while的判断条件，经过运算会正常跳到下一个位置。

用户头像
蛊惑角   5个月前         踩      回复

#include [HTML_REMOVED]
using namespace std;
vector[HTML_REMOVED]v;
int main()
{
int n,m,max;
string svr,fgh;
cin>>n;
while(n–){
cin>>svr;
m=1;
max=0;
v.push_back(m);
for(int i=1;i[HTML_REMOVED]max){
max=count(v.begin(),v.end(),v[i]);
fgh=svr[i];
}
i+=count(v.begin(),v.end(),v[i]);
}
cout<<fgh<<” “<<max<<endl;
v.clear();
}
return 0;
}

用户头像

大佬