Pythonで全ての母音を含む最長の美しい部分文字列の長さを求めるプログラム

問題の概要

英字の母音（a、e、i、o、u）のみで構成された文字列 s が与えられたとします。この中から「美しい部分文字列」の条件を満たす部分文字列のうち、最も長いものの長さを求めます。該当する部分文字列が存在しない場合は 0 を返します。

ここで「美しい文字列」とは、以下の2つの条件を満たす文字列のことです。

• 5種類の母音（a、e、i、o、u）がそれぞれ少なくとも1回以上出現すること
• 文字がアルファベット順（a → e → i → o → u）に並んでいること

例えば、入力が s = "aaioaaaaeiiouuooaauu" の場合、出力は 10 になります。これは部分文字列 "aaaaeiiouu" が美しい文字列の条件を満たしているためです。

解法のアプローチ

この問題は、2つのポインタ（左端 l と右端 r）を使った走査によって効率的に解くことができます。手順は以下の通りです。

1. 母音のリスト ['a', 'e', 'i', 'o', 'u'] を用意する
2. ポインタ l、r および答えとなる longest をすべて 0 で初期化する
3. l が文字列の長さ未満である間、以下を繰り返す
   • valid フラグを True で初期化する
   • 各母音について、現在位置 r の文字がその母音と一致しているかを確認し、一致する限り r を進める。母音の順序が崩れたり文字列の末尾に達した場合は valid を False にする
   • valid が True のままなら、その区間の長さ (r − l) と longest を比較し、大きい方を採用する
   • l を r に移動して次の候補区間へ進む
4. 最後に longest を返す

実装例

以下がPythonでの実装例です。

def solve(s):
    vowels = ['a', 'e', 'i', 'o', 'u']
    l, r, longest = 0, 0, 0
    while (l < len(s)):
        valid = True
        for vowel in vowels:
            valid &= (r < len(s) and s[r] == vowel)
            while (r < len(s) and s[r] == vowel):
                r += 1
        if (valid):
            longest = max(longest, r - l)
        l = r
    return longest

s = "aaioaaaaeiiouuooaauu"
print(solve(s))

入力

"aaioaaaaeiiouuooaauu"

出力

10

計算量について

このアルゴリズムでは、各文字はポインタ r によって最大1回しか訪問されないため、時間計算量は O(n)（n は文字列の長さ）になります。また、追加のデータ構造をほとんど必要としないため、空間計算量は O(1) と非常に効率的です。