Pythonで母音数が偶数の最長の部分文字列の長さを見つけるプログラム

文字列s（小文字）があるとすると、各母音が偶数回出現する最長の部分文字列の長さを見つける必要があります。

したがって、入力がs ="anewcoffeepot"の場合、サブストリング"wcoffeepot"には2つの母音"o"と"e"があり、どちらも2回発生するため、出力は10になります。

これを解決するには、次の手順に従います-

• 母音：=母音と数値を{a：0、e：1、i：2、o：3、u：4}として割り当てるマップ

• prefix：=空のマップで、キーと値のペア（0、-1）を挿入します

• マスク：=0、n：=sのサイズ、解像度：=0

• 0からnの範囲のiの場合、実行

  • s [i]が母音の場合、

    • mask：=mask XOR（2 ^ vowels [s [i]]）

  • マスクがプレフィックスにない場合は、

    • prefix [mask]：=i

  • それ以外の場合

    • res：=resの最大値と（i − prefix [mask]）

• 解像度を返す

理解を深めるために、次の実装を見てみましょう-

例

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