回文を部分文字列として含まない文にできるかどうか判定

Question

https://atcoder.jp/contests/cf17-final/tasks/cf17_final_b

自力では解けなかったので、こちらの問題を正解している方のわかりやすそうなコードをお借りして意味を理解しようと努めているのですがいくつか確認したい点があるので質問させてください。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    string S;
    cin >> S;
    
    vector<int> cnt(3, 0);
    for (int i=0;i< S.size();i++) cnt[S[i] - 'a']++;//1
    string ans = "YES";
    for (int i=0;i<3;++i){//2
      for (int j=0;j<3;++j){//2
        if (abs(cnt[i] - cnt[j]) > 1) ans = "NO";
      }
    }
    cout << ans << endl;
    return 0;
}

1.文字列S中に含まれるa,b,cという文字の個数をそれぞれカウントしているのでしょうか？
2.このiとjの二重ループはどういう意味なのでしょうか？またiとjが0から2までの3つなのはa,b,cの3つに対応しているということでしょうか？
以上になります。よろしくお願い致します。

Answer 1

1. その通りです。
2. 0,1,2はそれぞれ、a,b,cに対応しています。部分文字列として含まない文に出来る条件は、「各文字種の個数の差が1以下」なので、そのチェックを楽にやるため二重ループを使ったという解答ですね。なぜ各文字種の個数の差が1以下でなくてはいけないかは、AtCoder公式の解答pdfを見れば理解出来るかと思います。

Comments

[cunwe]

そういうことなのですね。その二重ループはなかなか自分では思いつかなそうですが、理解できました。ありがとうございました！