C++で文字列を変換して、すべての文字を一意にする方法

このチュートリアルでは、与えられた文字列を変換して、すべての文字が一意（重複なし）になるようにするC++プログラムについて解説します。

ここでは、小文字の英字からなる文字列が1つ与えられます。私たちのタスクは、文字列を先頭から順に走査し、2回以上出現している文字を、その時点で文字列内にまだ存在しない別の文字へ置き換えることです。

アルゴリズムのポイント

英小文字は26種類しか存在しないため、文字列の長さが26を超える場合には、どのように置き換えてもすべての文字を一意にすることはできません。そのようなケースでは「-1」を返す仕様になっています。

処理の流れは以下の通りです。

• 各文字（a〜z）の出現回数をサイズ26の配列に記録する
• 出現回数が0の文字（未使用の文字）を探して返す関数を用意する
• 文字列を走査し、出現回数が2以上の文字を見つけたら、未使用の文字に置き換えて出現回数を更新する

サンプルコード

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

// 出現回数が0（未使用）の文字を探して返す
int find_unused(int start, int occurrences[]) {
    for (int i = start; i < 26; i++) {
        if (occurrences[i] == 0)
            return i;
    }
    // 未使用の文字が存在しない場合
    return -1;
}

// 重複文字を置き換えた文字列を返す
string get_distinct_string(string str) {
    int n = str.length();
    // 英小文字は26種類なので、それより長い場合は変換不可
    if (n > 26)
        return "-1";
    string result = str;
    int occurrences[26] = {0};
    // 各文字の出現回数をカウント
    for (int i = 0; i < n; i++)
        occurrences[result[i] - 'a']++;
    int index = find_unused(0, occurrences);
    for (int i = 0; i < n; i++) {
        // 2回以上出現している文字を置き換える
        if (occurrences[result[i] - 'a'] > 1) {
            occurrences[result[i] - 'a']--;
            result[i] = (char)('a' + index);
            occurrences[index] = 1;
            // 次の未使用の文字を探す
            index = find_unused(index + 1, occurrences);
        }
    }
    return result;
}

int main() {
    string str = "tutorialspoint";
    cout << get_distinct_string(str) << endl;
    return 0;
}

出力

bucdrealspoint

コードの解説

入力文字列「tutorialspoint」には、「t」が3回、「o」と「i」がそれぞれ2回出現しています。プログラムはこれらの重複文字を先頭から順に検出し、まだ一度も使われていない文字（b、c、d、e…）へ置き換えていきます。その結果、すべての文字が一意となった文字列「bucdrealspoint」が出力されます。

計算量について見てみましょう。文字列の長さをNとすると、各文字のチェックごとに最大26文字分の走査が発生するため、全体の計算量はO(N×26)、つまり実質O(N)となります。追加のメモリもサイズ26の配列だけで済むため、非常に効率的な手法です。