C++で最短の「多数派」部分文字列の長さを求めるアルゴリズム

小文字アルファベットのみで構成された文字列 s が与えられたとします。このとき、ある1つの文字が他のすべての文字の合計よりも多く出現するような、最短の部分文字列(最小長は2)の長さを求める必要があります。条件を満たす部分文字列が存在しない場合は -1 を返します。

例えば、入力が "abbbcde" の場合、出力は 2 になります。これは部分文字列 "bb" が最短であり、この中では 'b' が他の文字より多く出現しているためです。

解法のアプローチ

この問題を解くためには、以下の手順に従います。

• 配列 cnt を受け取る関数 ok() を定義します。
• total := 0、maxVal := 0 と初期化します。
• cnt 内の各要素 it に対して以下を繰り返します。
  • total := total + it
  • maxVal := maxVal と it の最大値
• maxVal > (total − maxVal) が成り立つとき true を返します(つまり、最多の文字が残りの文字の合計を上回っているかを判定します)。

メイン処理の流れ

• n := 文字列 s の長さ
• ret := 無限大(INT_MAX)
• i := 0 から n 未満の間、i を1ずつ増やしながら以下を実行します。
  • i + 1 < n かつ s[i] == s[i + 1] の場合 → 長さ2の部分文字列で条件を満たすので、即座に 2 を返します。
  • そうでなく、i + 2 < n かつ s[i] == s[i + 2] の場合 → ret := 3 とします。
• 最後に、ret が INT_MAX のままなら -1 を、そうでなければ ret を返します。

なぜ長さ2と3だけ調べればよいのか

直感的には任意の長さの部分文字列を調べる必要があるように思えますが、実はそれほど手間はかかりません。ある部分文字列内で特定の文字が過半数を占めているならば、その部分文字列の両端を削っていっても過半数という性質は保たれます。したがって、条件を満たす部分文字列が存在するなら、必ず長さ2(隣接する同じ文字)または長さ3(1文字おきに同じ文字)のものが存在することになります。この性質により、線形時間 O(n) で答えを求められます。

実装例

理解を深めるために、以下の実装を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    bool ok(vector <int>& cnt){
        int total = 0;
        int maxVal = 0;
        for(auto& it : cnt){
            total += it;
            maxVal = max(maxVal, it);
        }
        return maxVal > (total - maxVal);
    }
    int solve(string s) {
        int n = s.size();
        int ret = INT_MAX;
        for(int i = 0; i < n; i++){
            if(i + 1 < n && s[i] == s[i + 1]){
                return 2;
            }else if(i + 2 < n && s[i] == s[i + 2]){
                ret = 3;
            }
        }
        return ret == INT_MAX ? -1 : ret;
    }
};
int main(){
    Solution ob;
    cout << (ob.solve("abbbcde"));
}

入力

"abbbcde"

出力

2

計算量について

このアルゴリズムは文字列を一度走査するだけで済むため、時間計算量は O(n)、追加の記憶領域も定数 O(1) と非常に効率的です。ok() 関数は一般の判定用として用意していますが、実際の solve() では隣接文字・1文字飛ばしの比較だけで十分に判定できる点がポイントです。