Pythonで最長の素晴らしい部分文字列を見つけるプログラム

数値文字列sがあるとします。私たちが知っているように、素晴らしい部分文字列はsの空でない部分文字列であり、回文にするために任意の数のスワップを行うことができます。 sの最大長の素晴らしい部分文字列の長さを見つける必要があります。

したがって、入力がs ="4353526"のような場合、 "35352"が最長の素晴らしい部分文字列であるため、出力は5になります。 「35253」回文を作成できます。

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

• n：=0

• pos_map：=キー0を含み、対応する値がsのサイズであるマップ

• max_len：=1

• s-1から0の範囲サイズのiの場合、1ずつ減らします。

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

  • nがpos_mapに存在する場合、

    • max_len：=max_lenとpos_map[n] -i

      の最大値

  • 0から9の範囲のjの場合、実行

    • m：=n XOR 2 ^ j

    • mがpos_mapにある場合、

      • max_len：=max_lenとpos_map[m] -i

        の最大値

  • nがpos_mapにない場合は、

    • pos_map [n]：=i

• max_lenを返す

例

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

def solve(s):
   n = 0
   pos_map = {0:len(s)}

   max_len = 1

   for i in range(len(s)-1, -1, -1):
      n = n ^ (1 << int(s[i]))

      if n in pos_map:
         max_len = max(max_len, pos_map[n]-i)

      for j in range(10):
         m = n ^ (1 << j)
         if m in pos_map:
            max_len = max(max_len, pos_map[m]-i)

      if n not in pos_map:
         pos_map[n] = i

   return max_len

s = "4353526"
print(solve(s))

入力

"4353526"

出力

5