Palindrome-phobia [CODE FESTIVAL 2017 Final B]

https://cf17-final-open.contest.atcoder.jp/tasks/cf17_final_b

解法

https://cf17-final-open.contest.atcoder.jp/submissions/1812665

文字列2文字の回文は"aa"である。
文字列3文字の回文は"a?a"である。
つまり、同じ文字は3つ以上離れている必要がある。
　
そう考えると、validな文字列は"abcabcabc..."のようにしか取れない。
「cnt[c] := 文字cの個数」とすると、validな文字列は以下の条件のいずれかをみたすものである。
　

• cnt[a] = cnt[b] = cnt[c]
• cnt[a] = cnt[b] + 1 = cnt[c] + 1
• cnt[a] = cnt[b] = cnt[c] + 1

　
これを確かめればよいのだが、1つ注意点があり、"abcabcabc..."以外にも"cbacbacba..."などもある。
これは全て試せばいい。

string S;
//---------------------------------------------------------------------------------------------------
#define yes "YES"
#define no "NO"
string solve() {
    map<char, int> cnt;
    fore(c, S) cnt[c]++;

    vector<char> v;
    rep(i, 0, 3) v.push_back(char('a' + i));
    do {
        char c0 = v[0], c1 = v[1], c2 = v[2];

        if (cnt[c0] == cnt[c1] and cnt[c1] == cnt[c2]) return yes;
        if (cnt[c0] == cnt[c1] + 1 and cnt[c1] + 1 == cnt[c2] + 1) return yes;
        if (cnt[c0] == cnt[c1] and cnt[c1] == cnt[c2] + 1) return yes;
    } while (next_permutation(v.begin(), v.end()));

    return no;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> S;
    cout << solve() << endl;
}