C++で文字列が「多様（ダイバース）」かどうかを判定する方法

問題の概要

小文字の英字からなる長さ n の文字列 S が与えられたとします。このとき、次の条件をすべて満たす文字列を「多様な文字列（diverse string）」と呼びます。

• アルファベットが連続して並んでいること
• それぞれの文字がちょうど1回だけ出現すること
• なお、「a」と「z」は隣接しているものとはみなさない

この記事では、与えられた文字列 S が多様な文字列であるかどうかを C++ で判定する方法を解説します。

例えば、入力が S = "fced" の場合、文字を並べ替えると c, d, e, f となり、アルファベットが連続しているため、出力は True（1）になります。

解き方の手順

この問題は、以下の手順で解くことができます。

1. 文字列 S を昇順にソートする
2. フラグ変数 flag を 1 で初期化する
3. i を 1 から開始し、i が S のサイズ未満かつ flag が 0 でない間、次の処理を繰り返す
   　・S[i] − S[i − 1] が 1 ではない場合、flag を 0 に設定する
4. flag が 0 以外であれば true、そうでなければ false を返す

実装例

理解を深めるために、実際の C++ コードを見てみましょう。

#include <bits/stdc++.h>
using namespace std;
bool solve(string S){
    sort(S.begin(), S.end());
    int flag = 1;
    for (int i = 1; i < S.size() && flag; i++)
       if (S[i] - S[i - 1] != 1)
          flag = 0;
    return flag ? true : false;
}
int main(){
    string S = "fced";
    cout << solve(S) << endl;
}

入力

"fced"

出力

1

まとめ

このアルゴリズムのポイントは、まず文字列をソートすることです。多様な文字列であれば、ソート後は必ず「b, c, d…」のように隣接する文字同士の差が 1 になります。そのため、隣接する文字の差分を順番にチェックするだけで判定できます。

計算量は、ソート部分が O(n log n)、比較部分が O(n) となり、非常に効率的な手法です。文字列操作の基礎的な練習問題として、ぜひ参考にしてください。