C++でアルファベット順に並ぶ部分文字列の個数を求める方法

問題の概要

長さ n の文字列を考えます。この文字列には大文字のアルファベットのみが含まれており、その中から「各文字がアルファベット順（A→B→C…）に連続して並んでいる」部分文字列の個数を求めます。なお、部分文字列の最小サイズは 2 とします。

例えば、文字列が「REFJHLMNBV」の場合、条件を満たす部分文字列は「EF」と「MN」の 2 つとなります。

解決のための手順

この問題は、文字列を一度走査するだけで効率的に解くことができます。手順は以下の通りです。

• 隣り合う文字同士を比較し、str[i] + 1 が str[i + 1] と等しい（＝文字コード上で1つずつ連続している）かどうかを確認します。
• 等しい場合は、結果カウントを 1 増やし、アルファベット順から外れる文字が現れるまでインデックスを読み進めて、連続した並びをひとまとまりとして処理します。
• 等しくない場合は、そのまま次の文字へ移動します。

この手法により、計算量は O(n) となり、長い文字列でも高速に処理できます。

サンプルコード

#include<iostream>
using namespace std;
int countSubstr(string main_str) {
    int res = 0;
    int n = main_str.size();
    for (int i = 0; i < n - 1; i++) {
        if (main_str[i] + 1 == main_str[i + 1]) {
            res++;
            while (main_str[i] + 1 == main_str[i + 1]) {
                i++;
            }
        }
    }
    return res;
}
int main() {
    string str = "REFJHLMNBV";
    cout << "Number of substrings: " << countSubstr(str);
}

実行結果

Number of substrings: 2

コードのポイント

外側の for ループで文字列全体を走査し、連続するアルファベットを見つけた時点でカウントを 1 増やした後、内側の while ループでその連続部分を一気にスキップしています。これにより、同じ並びを二重に数えてしまうことを防いでいます。上記の例では「REFJHLMNBV」の中に「EF」と「MN」の 2 箇所が該当するため、出力は 2 になります。