AtCoder ABC 044 B - 美しい文字列 (6Q, 灰色, 200 点)

集計処理系の良問！

• 問題へのリンク

問題概要

英小文字からなる文字列 について、どの英小文字も登場回数が偶数回であるかどうかを判定せよ。

制約

• 

解法 (1)：各文字について登場回数を見ていく

まずは愚直な解法を考えよう。文字 = 'a', 'b', ..., 'z' について、文字列 上に何回登場するかを数えてあげて、それらが偶数であるかどうかを判定すればよい。

コード

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

int main() {
    string S;
    cin >> S;

    bool res = true;
    for (char c = 'a'; c <= 'z'; ++c) {
        // 文字 c が何回登場したかを数える
        int con = 0;
        for (int i = 0; i < S.size(); ++i) {
            if (S[i] == c) ++con;
        }

        // con が奇数はダメ
        if (con % 2 == 1) res = false;
    }

    cout << (res ? "Yes" : "No") << endl;
}

解法 (2)：バケットを作る

次のような配列を用意しよう。

---

• con[c] ← 文字 が文字列 中に何回登場するか

---

この配列は一回だけ for 文を回して文字列 の各文字を走査するだけで作れる！　なお、配列を作る際には、文字 'a', 'b', ..., 'z' をそれぞれ 0, 1, ..., 25 に対応させることにする。

この配列を作ってしまえば、あとは、各文字 に対して、con[c] が偶数であるかを判定すればよい。

コード

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

int main() {
    string S;
    cin >> S;

    vector<int> con(26, 0);
    for (int i = 0; i < S.size(); i++) {
        con[S[i] - 'a']++;
    }

    bool res = true;
    for (int i = 0; i < 26; ++i) if (con[i] % 2 == 1) res = false;

    cout << (res ? "Yes" : "No") << endl;
}