C++で文字列の各文字より右側にある大きい要素の数を数える方法

文字列が与えられたとき、各文字について「その文字より右側に存在する、より大きい要素（文字）」の数を数える問題を考えてみましょう。まずは具体例を見てみます。

入力

string = "abc"

出力

2 1 0

この結果は次のように解釈できます。

• a の右側には a より大きい文字が 2 つあります。
• b の右側には b より大きい文字が 1 つあります。
• c の右側には c より大きい文字は 0 個です。

アルゴリズム

• 文字列を初期化します。
• 各文字のカウントを記録するための配列を用意します。
• 二重ループを使って文字列を走査します。
  • 一度に 1 文字ずつ取り出し、それ以降のすべての文字と比較します。
  • 現在の文字が比較対象の文字より小さい場合、対応するカウントを 1 増やします。
• すべての文字のカウント結果を出力します。

この手法は単純な全探索であり、時間計算量は O(n²) となります。文字列が短い場合には十分実用的ですが、長い文字列に対しては後述のような工夫が必要になることもあります。

C++での実装

以下は、上記のアルゴリズムを C++ で実装したコードです。

#include <bits/stdc++.h>
using namespace std;
void countCharNextLargerElementsCount(string str) {
    int len = str.length(), count[len];
    for (int i = 0; i < len; i++) {
        count[i] = 0;
    }
    for (int i = 0; i < len; i++) {
        for (int j = i + 1; j < len; j++) {
            if (str[i] < str[j]) {
                count[i]++;
            }
        }
    }
    for (int i = 0; i < len; i++) {
        cout << count[i] << " ";
    }
    cout << endl;
}
int main() {
    string str = "abcdefgh";
    countCharNextLargerElementsCount(str);
    return 0;
}

実行結果

上記のコードを実行すると、次の出力が得られます。

7 6 5 4 3 2 1 0

入力文字列 "abcdefgh" は昇順に並んでいるため、先頭の 'a' の右側には 7 個の大きい文字があり、末尾の 'h' の右側には 0 個となっています。このように、各位置における右側の大きい文字数が順に出力されます。