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

数値文字列 s が与えられたとします。ここで「素晴らしい部分文字列（awesome substring）」とは、s の空でない部分文字列のうち、文字の入れ替え（スワップ）を何度行ってもよいとして回文にできるものを指します。この記事では、s に含まれる最長の素晴らしい部分文字列の長さを求める方法を解説します。

例えば、入力が s = "4353526" の場合、出力は 5 になります。「35352」が最長の素晴らしい部分文字列であり、文字を並べ替えることで「35253」という回文を作れるからです。

回文にできる条件とは？

文字を自由に入れ替えられる場合、ある文字列が回文にできるかどうかは、各文字の出現回数の偶奇だけで決まります。

• すべての文字が偶数回出現 → 回文にできる
• 奇数回出現する文字がちょうど1種類だけ → 回文にできる（中央に配置）
• 奇数回出現する文字が2種類以上 → 回文にできない

したがって問題は、「奇数回出現する数字が高々1種類である最長の部分文字列」を探す問題に言い換えられます。

解法のアプローチ：ビットマスクと累積XOR

各数字（0〜9）に対応するビットを用意し、出現回数の偶奇を10ビットの整数（ビットマスク）で管理します。累積XORを利用すると、任意の区間内での各数字の偶奇を高速に求められます。

アルゴリズムの手順

• n := 0（現在のビットマスク）
• pos_map := {0: len(s)} — マスクの値ごとに最初に現れた位置を記録するマップ
• max_len := 1
• i を len(s)-1 から 0 まで1ずつ減らしながら繰り返す：
  • n := n XOR (2^s[i]) — 現在の文字のビットを反転
  • n が pos_map に存在すれば、max_len := max(max_len, pos_map[n] - i)
  • j を 0〜9 まで繰り返し：
    • m := n XOR 2^j — 1文字だけ奇数になるケースを許容
    • m が pos_map に存在すれば、max_len := max(max_len, pos_map[m] - i)
  • n が pos_map に存在しなければ、pos_map[n] := i
• max_len を返す

この手法により、全部分文字列を総当たりする O(N²) を大幅に上回る効率で、時間計算量 O(10×N)、空間計算量 O(2¹⁰) で解くことができます。

Pythonでの実装例

以下のコードで実際の動作を確認してみましょう。

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

まとめ

この問題のポイントは、回文の成立条件を「奇数回出現する文字が高々1種類」という偶奇の問題に変換することです。ビットマスクと累積XORを組み合わせることで、各マスク状態の最初の出現位置を記録しておき、差分から最長の部分文字列の長さを効率的に求められます。同様のテクニックは「奇偶性を扱う部分配列・部分文字列の問題」全般に応用できるので、ぜひ覚えておきましょう。