ABC329 C問題 Count xxx

はじめに

自分の理解度を高めるために解法を置いておきます。参考になればうれしいです。

解く問題

C - Count xxx

大切なこと

まず、文字列の長さが最大2*10^5になります。AtCoderは意地悪なのでこれを普通に入力で与えてきます。
この問題の実行時間制限は2secです。なのでO(N^2)を超える、あり得るすべてのパターンをすべて見て、そこから答えを求めるといった解き方はできません。

具体的な解き方

長さNの文字列中に、あるアルファベットで構成された長さn (1≤n≤N)の部分文字列があると仮定します。
この時、部分文字列の文字は全て同じであるという条件から、文字列の中に長さ 1, 2, 3, … ,nの部分文字列もあると考えられます。
文字列の重複は考慮しないので、あるアルファベットの部分文字列の長さがそのまま、そのアルファベット長さNの文字列内に含まれる部分文字列の種類数になります。

まとめると
あるアルファベットの部分文字列の最大長さをすべて足し合わせたら、答えになります。

これはmapを用いると実装ができます。

答え

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<long double,long double>;
using ull = unsigned long long;

int main()
{
int N;
cin >> N;
string str;
cin >> str;
set<string> check;
map<char,int> mp;

for(int i=0;i<N;i++){
    char flag=str[i];
    if(!mp.count(flag)) mp[flag]=1;
    int temp=0;
    int j=i;
    while(j<N && flag==str[j]){
        temp++;
        if(temp>mp[flag]) mp[flag]++;
        j++;
    }
    i=j-1;
}
ll ans=0;
for(auto a:mp) ans+=a.second;
cout << ans << endl;
}

個人的に気を付けるべき点として、if(temp>mp[flag]) mp[flag]++;の点です。
tempにはiからjまでの部分文字列長が保存されています。そしてmp[flag]はj文字目までの最大部分文字列長が保存されています。tempを用いず都度mp[flag]++;を行うと"bbgbb"というような文字列でバグが起きるのでtempがmp[flag]を超えた場合に更新を行うようにしています。