AtCoder ABC 063 B - Varied (6Q, 灰色, 200 点)

とても教育的な易しい問題！

• 問題へのリンク

問題概要

英小文字からなる文字列 が与えられる。

の文字がすべて互いに相異なるかどうかを判定せよ。

解法 (1)：多重 for 文

最も素朴な方法は、 から 2 文字を選ぶ方法をすべて試して、「それらが異なっているか」を調べていく方法だ。もし、この過程で、等しいペアが見つかったら "no" となる。

#include <bits/stdc++.h>
using namespace std;
                                 
int main() {
    string S;
    cin >> S;

    bool res = true;
    for (int i = 0; i < S.size(); i++) {
        for (int j = i+1; j < S.size(); j++) {
            // S 内の文字 S[i], S[j] が等しいとダメ
            if (S[i] == S[j]) res = false;
        }
    }

    if (res) cout << "yes" << endl;
    else cout << "no" << endl;
}

解法 (2)：バケットを使う

もう 1 つ応用の利く方法をやってみよう。それは、次のような配列を作ることだ。

---

• num[c]：文字列 に含まれる文字 の個数

---

このように、値ごとに集計するような配列をバケットということがある。なお、実際にこの配列を作るときには、文字 'a' を 0 に対応させて、文字 'b' を 1 に対応させて、...文字 'z' を 25 に対応させよう。

#include <bits/stdc++.h>
using namespace std;
                                 
int main() {
    string S;
    cin >> S;

    vector<int> num(26, 0);
    for (int i = 0; i < S.size(); i++) {
        num[S[i] - 'a']++;
    }
    bool res = true;
    for (int i = 0; i < 26; i++) if (num[i] > 1) res = false;

    if (res) cout << "yes" << endl;
    else cout << "no" << endl;
}

解法 (3)：ソートする

最後に、ソートする方法を考えよう。ソートすると、もし文字列中に同じ文字があれば、「同じ文字は連続する」ようになる。

このことを利用して、ソート後に

• 隣接する 2 文字がすべて、互いに相異なるとき："yes"
• 隣接する 2 文字で等しいもんごああるとき："no"

と判定すればよい。

#include <bits/stdc++.h>
using namespace std;
                                 
int main() {
    string S;
    cin >> S;

    sort(S.begin(), S.end());

    // 同じ文字が隣接しないことを確かめる
    bool res = true;
    for (int i = 0; i + 1 < S.size(); i++) {
        if (S[i] == S[i+1]) res = false;
    }

    if (res) cout << "yes" << endl;
    else cout << "no" << endl;
}