C++で各母音が偶数回出現する最長部分文字列を求める方法

問題の概要

文字列 s が与えられたとき、「各母音が偶数回出現する」最長の部分文字列の長さを求めます。つまり、'a'、'e'、'i'、'o'、'u' のそれぞれが、部分文字列内に必ず偶数回現れる必要があります。

例として、文字列が "helloworld" の場合、答えは 8 になります。

アルゴリズムの考え方

この問題は、各文字を読み進めながら「母音の偶奇の状態」を記録していくことで効率的に解けます。5つの母音それぞれについて出現回数が偶数か奇数かを 0 と 1 で表し、これを "01010" のような 5 文字の状態文字列として管理します。

同じ状態文字列が 2 回現れた場合、その間の部分文字列では各母音の出現回数の偶奇が変化していないことになります。これは、その区間内で各母音が偶数回出現していることを意味します。したがって、各状態が最初に現れた位置をマップに記録しておき、同じ状態が再び現れたときにその距離を計算すれば、最長の部分文字列の長さが求まります。

解法の手順

• ret := 0 とし、2つのマップ m と cnt を定義します。さらに m["00000"] := -1 と設定します(先頭から現在位置までの部分文字列を考慮するための初期化です)。
• 母音を配列 vowels に格納します。
• i を 0 から s のサイズまで繰り返します。
  • x := s[i] とし、cnt[x] を 1 増やします。
  • 空文字列 temp を用意し、k を 0 から 4 までループして、temp := temp + ('0' + cnt[vowels[k]] mod 2) として状態文字列を構築します。
  • m に temp が既に存在すれば ret := max(ret, i - m[temp]) と更新し、存在しなければ m[temp] := i として位置を記録します。
• 最後に ret を返します。

C++による実装例

以下に実際の実装を示します。

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int findTheLongestSubstring(string s) {
      int ret = 0;
      map <string, int> m;
      map <char, int> cnt;
      m["00000"] = -1;
      char vowels[5] = {'a', 'e', 'i', 'o', 'u'};
      for(int i = 0; i < s.size(); i++){
         char x = s[i];
         bool ok = false;
         cnt[x]++;
         string temp = "";
         for(int k = 0; k < 5; k++){
            temp+= ('0' + (cnt[vowels[k]] % 2));
         }
         if(m.count(temp)){
            ret = max(ret, i - m[temp]);
         }
         else{
            m[temp] = i;
         }
      }
      return ret;
   }
};
main(){
   Solution ob;
   cout << (ob.findTheLongestSubstring("helloworld"));
}

入力例

"helloworld"

出力例

8

計算量と最適化のポイント

文字列を一度走査するだけなので、時間計算量は O(n) です。また、母音の偶奇状態の組み合わせは 2⁵ = 32 通りしか存在しないため、マップに保存されるエントリは最大でも 32 個であり、空間計算量は実質 O(1) とみなせます。

さらに最適化したい場合は、状態文字列の代わりに 5 ビットの整数(ビットマスク)を使うと、文字列の構築コストがなくなり、より高速に動作します。