【C++】文字列内のすべての異なる文字を出現順に出力する方法

問題概要

この問題では、1つの文字列が与えられます。求められているのは、その文字列に含まれるすべての異なる文字(重複していない文字)を、元の文字列での出現順に従って出力することです。

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

入力: tutorials Point
出力: uralsPn

「t」や「o」、「i」などは複数回出現するため除外され、1度だけ登場する文字だけが出現順に表示されていることがわかります。

解法のアプローチ

この問題には複数の解き方があります。最も単純なのは二重ループ(ネストされたループ)を使う方法ですが、計算量がO(n²)となり、文字列が長くなると非効率です。

そこで本記事では、より効率的な線形時間O(n)の解法を紹介します。この解法では、サイズ256の整数型配列を2つ使用します(8ビット文字のコード値0〜255に対応させるためです)。

アルゴリズムの手順

1. カウント用配列countの全要素を0で初期化し、インデックス用配列indexの全要素を文字列長nで初期化します。
2. 文字列strを先頭から走査し、各文字xについてcount[x]を1ずつ増加させます。
3. count[x]が1になった場合(初めて出現したとき)、index[x]にその位置iを記録します。
4. count[x]が2になった場合(2回目以降の出現)、index[x]をnに戻し、重複文字として除外対象にします。
5. 最後にindex配列を昇順にソートし、n以外の値(=有効なインデックス)に対応する文字を順に出力します。

インデックスをソートすることで、文字列中の出現順序が自然に保たれるのがこの手法のポイントです。

実装例

上記の解法を実装したC++コードは以下の通りです。

#include <bits/stdc++.h>
using namespace std;
const int MAX_CHAR = 256;
void printDistinctCharacters(string str) {
   int n = str.length();
   int count[MAX_CHAR];
   int index[MAX_CHAR];
   for (int i = 0; i < MAX_CHAR; i++) {
      count[i] = 0;
      index[i] = n;
   }
   for (int i = 0; i < n; i++) {
      char x=str[i];
      ++count[x];
      if (count[x] == 1 && x !=' ')
         index[x] = i;
      if (count[x] == 2)
         index[x] = n;
   }
   sort(index, index+MAX_CHAR);
   for (int i=0; i<MAX_CHAR && index[i] != n; i++)
   cout<<str[index[i]]<<" ";
}
int main() {
   string str = "tutorialsPoint";
   cout<<"All distinct Characters of the string '"<<str<<"' are :\n";
   printDistinctCharacters(str);
   return 0;
}

出力結果

All distinct Characters of the string 'tutorialsPoint' are −
u r a l s P n

まとめ

この解法は、文字列を1回走査するだけで済むため、時間計算量はO(n + MAX_CHAR log MAX_CHAR)(ソート部分)、空間計算量はO(MAX_CHAR)となります。二重ループを使う素朴な手法と比べて大幅に高速であり、長い文字列を扱う場合に特に有効です。頻度カウントとインデックス管理を組み合わせるテクニックは、他の文字列処理の問題にも応用できるので、ぜひ覚えておきましょう。