C++で文字列内の重複文字とその出現回数を出力する方法

この問題では、与えられた文字列の中から重複しているすべての文字を検出し、それぞれの出現回数とともに出力する必要があります。

問題の理解

まず、具体例を使って問題を確認してみましょう。

入力：TutorialsPoint

出力：
t (3)
o (2)
i (2)

解説：各文字の出現回数を数えると、以下のようになります。

• t → 3回
• u → 1回
• o → 2回
• r → 1回
• i → 2回
• a → 1回
• s → 1回
• n → 1回

この結果から、出現回数が2回以上の文字（t、o、i）だけが出力対象となります。

解決のアプローチ

この問題を解くための手順は以下の通りです。

1. 文字列を先頭から走査し、各文字の出現回数をカウントします。
2. カウント結果を、ASCIIコードに対応したサイズ256の整数型配列に格納します。
3. 配列を走査し、出現回数が1より大きい文字とその回数を出力します。

ASCII文字は最大256種類あるため、サイズ256の配列を用意することで、あらゆる半角英数字・記号に対応できます。

C++による実装例

#include <iostream>
using namespace std;
#define NO_OF_CHARS 256

class duplicate_char {
public:
    // 各文字の出現回数をカウントする関数
    void charCounter(char *str, int *count) {
        int i;
        for (i = 0; *(str + i); i++)
            count[*(str + i)]++;
    }

    // 重複文字を出力する関数
    void printDuplicateCharacters(char *str) {
        int *count = (int *)calloc(NO_OF_CHARS, sizeof(int));
        charCounter(str, count);
        int i;
        for (i = 0; i < NO_OF_CHARS; i++)
            if (count[i] > 1)
                printf("%c\t\t %d \n", i, count[i]);
        free(count);
    }
};

int main() {
    duplicate_char dupchar;
    char str[] = "tutorialspoint";
    cout << "The duplicate characters in the string\n";
    cout << "character\tcount\n";
    dupchar.printDuplicateCharacters(str);
    return 0;
}

実行結果

The duplicate characters in the string
character　count

i   2
o   2
t   3

コードのポイント

• charCounter関数：文字列を1文字ずつ読み込み、その文字のASCIIコードをインデックスとして配列countの値を増やしていきます。
• calloc関数：メモリを確保すると同時に0で初期化するため、カウント用配列の初期化が不要になります。
• free関数：動的に確保したメモリを解放し、メモリリークを防ぎます。

このアルゴリズムの計算量は、文字列の長さをNとすると O(N + 256)、つまり実質 O(N) となり、非常に効率的です。大文字と小文字を区別せずにカウントしたい場合は、toupper() や tolower() を使って文字を正規化してからカウントするとよいでしょう。