C++で長さkの部分文字列に含まれる母音の最大数を求める方法

文字列 s と整数 k が与えられたとき、長さがちょうど k である s の部分文字列の中に、母音（a, e, i, o, u）が最大でいくつ含まれるかを求める問題です。

例えば、入力が s = "abciiidef"、k = 3 の場合、出力は 3 になります。これは、部分文字列 "iii" に母音が3つ含まれているためです。

解法アプローチ：スライディングウィンドウ（尺取り法）

この問題は「スライディングウィンドウ」と呼ばれる手法を使うことで、文字列全体を一度走査するだけで効率的に解くことができます。各ステップでウィンドウの右端に新しい文字を追加し、左端から古い文字を取り除くことで、毎回母音を数え直す無駄を省きます。

具体的な手順は以下の通りです。

• 母音カウンター cnt を 0 で初期化する
• 母音を格納するセット m を定義し、a, e, i, o, u を挿入する
• 結果を保持する変数 ret を 0 で初期化する
• 最初のウィンドウ（先頭から k 文字）に含まれる母音の数を数えて cnt に加算する
• ret と cnt の大きい方を ret に代入する
• 文字列の長さを n とする
• i を k から n-1 まで増やしながら以下を繰り返す
  • ウィンドウから外れる文字 s[i-k] が母音なら cnt を1減らす
  • ウィンドウに入る文字 s[i] が母音なら cnt を1増やす
  • ret と cnt の大きい方を ret に代入する
• 最後に ret を返す

C++での実装例

それでは、実際のコードを見て理解を深めましょう。

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    int maxVowels(string s, int k) {
        int cnt = 0;
        set<char> m;
        for (auto it : { 'a', 'e', 'i', 'o', 'u' })
        m.insert(it);
        int ret = 0;
        for (int i = 0; i < k; i++) {
            cnt += m.count(s[i]) ? 1 : 0;
        }
        ret = max(ret, cnt);
        int n = s.size();
        for (int i = k; i < n; i++) {
            if (m.count(s[i - k])) {
                cnt--;
            }
            cnt += m.count(s[i]) ? 1 : 0;
            ret = max(ret, cnt);
        }
        return ret;
    }
};
main(){
    Solution ob;
    cout << (ob.maxVowels("abciiidef",3));
}

入力

"abciiidef", 3

出力

3

計算量の分析

• 時間計算量： O(n) ― 文字列を一度だけ走査すればよいため、非常に高速です。
• 空間計算量： O(1) ― 母音のセットは固定サイズ（5要素）であり、追加のメモリはほとんど不要です。

もし素朴なアプローチ（すべての長さ k の部分文字列に対して毎回母音を数え直す）を採用すると、時間計算量は O(n × k) になってしまいます。スライディングウィンドウを使うことで、これを O(n) まで大幅に改善できるのがこの手法の大きな利点です。