AtCoder ABC 329 C - Count xxx (灰色, 300 点)

ランレングス圧縮の典型題！　なお、ランレングス圧縮は鹿本でみっちり解説している。

• 問題へのリンク

問題概要

英小文字のみからなる長さ の文字列 が与えられる。

の連続する部分文字列のうち、1 種類の文字のみからなる文字列の種類数を答えよ。

制約

• 

考えたこと

アルファベットは 26 文字あるが、各文字について、その文字が最長で何個連続しているかを求めればよい。たとえば

= "aaabbaaaaacaa"

の場合、文字 'a' は最長で 5 個連続している。よって、文字 'a' からなる部分文字列は

• "a"
• "aa"
• "aaa"
• "aaaa"
• "aaaaa"

の 5 種類となる。

ランレングス圧縮

各文字が最長で何個連続しているかを求めるためには、ランレングス圧縮が有効である。たとえば、文字列

= "aaabbaaaaacaa"

に対して、次のような変換を施す。同じ文字が連続している箇所に対して、(その文字, 連続個数) という情報に圧縮するイメージだ。

('a', 3), ('b', 2), ('a', 5), ('c', 1), ('a', 2)

この処理をランレングス圧縮という。同じ文字が連続している箇所が多いほど圧縮効率が良くなる。

さて、ランレングス圧縮すれば、各文字が最長で何個連続しているかが求められる。それを各文字に対して総和をとればよい。ランレングス圧縮に要する計算量は であるから、計算量は となる。

なお、ランレングス圧縮は毎回決まった形で書けるので、スラスラ書けるようにしておきたいし、ライブラリ化しても良いと思う。

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N;
    string S;
    cin >> N >> S;
    
    // 各文字について最長記録を求める
    vector<int> len(26, 0);
    
    // ランレングス圧縮していく
    for (int i = 0; i < N; ) {
        char c = S[i];
        int j = i;
        while (j < N && S[j] == c) ++j;
        
        // 区間 [i, j) が文字 c である
        len[c - 'a'] = max(len[c - 'a'], j - i);
        
        // i を j にセットする
        i = j;
    }
    
    // 各文字の最長長さを足していく
    int res = 0;
    for (int i = 0; i < 26; ++i) res += len[i];
    cout << res << endl;
}