問題

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

$s$ の空でない部分文字列について、1種類の文字からなるものの個数を求めよ。

ただし、 $s$ の空でない部分文字列とは「 $s$ の先頭から $0$ 字以上、末尾から $0$ 字以上削除して得られる文字列のうち、長さが1以上の文字列」のことを指す。

また、部分文字列として等しいものについては区別しないこと。

入力

最初の1行に整数 $n$ が、次の1行に文字列 $s$ が与えられる。

条件

$1 \leq n \leq {2} \times {10}^{5}$
$s$ は英小文字からなる長さ $n$ の文字列である。

出力

$s$ の空でない部分文字列のうち、1種類の文字からなるものの個数を1行で出力すること。

解法

条件より、 $s$ の部分文字列に対して等しいものについては区別をしません。

例えば、 $s=$ aaa である場合、先頭の2文字の aa と末尾の2文字の aa は同じものとしてカウントされます。このことに注意すると、この場合では a, aa, aaa の3個が答えとなります。

さらに、 $s=$ aaabbaa である場合について、

最初の1つ目の a の部分については、 a, aa, aaa の3種類
次の b の部分については、 b, bb の2種類
次の2つ目の a の部分については、a, aa の2種類

ということから、a, aa, aaa, b, bb の5個がこの場合の答えとなります。

以上から、 $s$ の各文字を先頭から見ていき、 a から z までの各小文字について、連続してその文字が続く部分の長さの最大値の合計が答えとなります。

ソースコード

以下のようにして、 main() 関数に直接答えを出力できるように実装しました。

int n, cnt[26]; // cnt は26種類の文字について、連続する長さの最大値を保存するための配列
string s;

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

  int now_cnt = 1; // 現状の文字での連続する長さを表す
  cnt[s[0] - 'a'] = 1; // 最初の1文字目について、cnt の値を更新する

  for (int i = 1; i < n; i++) {
    if (s[i] != s[i - 1]) {
      now_cnt = 1; // もし、前の文字と現在の文字が異なるならば、 now_cnt は 1 にリセットする
    } else {
      now_cnt++; // 前の文字と現在の文字が同じならば、 now_cnt を 1 増やす
    }

    cnt[s[i] - 'a'] = max(cnt[s[i] - 'a'], now_cnt); // 現在の文字について、配列に保存された値を now_cnt を比較して、 cnt を更新する
  }

  int ans = 0; // 答えを表す整数 ans を宣言する
  for (int i = 0; i < 26; i++) {
    ans += cnt[i]; // ans に26種類分の cnt を加えていく
  }
  cout << ans << endl; // ans を出力する

  return 0;
}