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; }