【Python】各母音が偶数回出現する最長部分文字列の長さを求めるアルゴリズム

問題の概要

小文字のみで構成された文字列 s が与えられたとき、すべての母音（a, e, i, o, u）がそれぞれ偶数回出現する最長の部分文字列の長さを求めることを考えます。

例えば、入力が s = "anewcoffeepot" の場合、出力は 10 になります。これは、部分文字列 "wcoffeepot" に含まれる母音が "o" と "e" の2種類であり、どちらも2回ずつ出現しているためです。

解法のアプローチ：ビットマスクとハッシュマップの活用

この問題は、ビットマスク（bitmask）とハッシュマップを組み合わせることで、O(n) の計算量で効率的に解くことができます。

基本的な考え方は次の通りです。

• 5つの母音 a, e, i, o, u に対して、{a:0, e:1, i:2, o:3, u:4} のように番号を割り当てます。
• 現在位置までの母音の出現状況を「パリティ（偶奇）」としてビットマスクで管理します。ある母音が出現するたびに、対応するビットを XOR 演算で反転させます。
• 同じマスク値が再び現れた場合、その間の区間ではすべての母音が偶数回出現していることになります。したがって、そのマスクが最初に現れた位置との距離が答えの候補になります。

アルゴリズムの手順

• vowels := 母音と数値を対応付けたマップ {a:0, e:1, i:2, o:3, u:4} を作成
• prefix := 空のマップを用意し、初期値としてキーと値のペア (0, −1) を挿入
• mask := 0、n := 文字列 s の長さ、res := 0 で初期化
• i を 0 から n−1 まで繰り返す：
• s[i] が母音である場合、mask := mask XOR (2^vowels[s[i]]) を実行
• mask が prefix に存在しない場合、prefix[mask] := i を記録
• すでに存在する場合、res := max(res, i − prefix[mask]) で最大長を更新
• 最後に res を返す

Pythonでの実装例

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

class Solution:
    def solve(self, s):
        vowels = {"a": 0, "e": 1, "i": 2, "o": 3, "u": 4}
        prefix = {0: -1}
        mask = 0
        n = len(s)
        res = 0
        for i in range(n):
            if s[i] in vowels:
                mask ^= 1 << vowels[s[i]]
            if mask not in prefix:
                prefix[mask] = i
            else:
                res = max(res, i - prefix[mask])
        return res

ob = Solution()
s = "anewcoffeepot"
print(ob.solve(s))

入力

"anewcoffeepot"

出力

10

コードのポイント解説

1. prefix = {0: -1} の初期化について
マスクが 0（すべての母音が偶数回出現している状態）は「文字列の開始前」にも存在するとみなすための初期化です。これにより、文字列の先頭から始まる有効な部分文字列も正しく計算できるようになります。

2. XOR演算の役割
同じ母音が2回出現すると、対応するビットが反転して元に戻ります。この性質により、偶数回の出現は自動的に打ち消し合い、現在の母音の偶奇だけがマスクに反映されます。

3. 計算量
文字列を一度走査するだけでよいため、時間計算量は O(n)、ハッシュマップのサイズはマスクの状態数に依存するため空間計算量も O(n) となります。全ての部分文字列を調べる総当たり法（O(n²)〜O(n³)）と比べて大幅に高速です。