Pythonで文字列を一意な部分文字列に分割したときの最大数を求める方法

文字列 s が与えられたとき、その文字列を分割して得られる一意な部分文字列の最大数を見つける必要があります。文字列 s は、空でない部分文字列のリストに自由に分割でき、それらを連結すると元の文字列と一致しなければなりません。ただし、分割後のすべての部分文字列は互いに重複してはならず、すべて異なるものである必要があります。

たとえば、入力が s = "pqpqrrr" の場合、出力は 5 になります。これは ["p", "q", "pq", "r", "rr"] のように分割できるためです。一方、["p", "q", "p", "q", "r", "rr"] のような分割は無効です。この場合、"p" と "q" が複数回現れているためです。

解決アプローチ

この問題を解くために、以下の手順に従います。

• res := 要素が 0 のみのリストとして初期化する
• 関数 dfs() を定義する。引数として s と、新しい空の集合 path を受け取る
• s が空の場合：
  • res[0] := res[0] と path のサイズのうち大きい方を代入する
  • 処理を終了して戻る
• i を 1 から s のサイズまで繰り返す：
  • x := s の先頭から i 文字目までの部分文字列
  • x が path に含まれていない場合：
    • dfs(s の i 文字目以降の部分文字列, path ∪ {x}) を再帰的に呼び出す
• メイン処理では以下を実行する：
• dfs(s) を呼び出す
• res[0] を返す

アルゴリズムのポイント

この手法はバックトラッキング（深さ優先探索：DFS）を活用しています。文字列の先頭から可能なすべての切り分け位置を順に試し、すでに使用した部分文字列を path という集合で管理することで重複を防止します。文字列を使い切った時点での path のサイズが、その分割経路における一意な部分文字列の個数に相当するため、その最大値を res[0] に記録し続けます。考えられる分割パターンをすべて網羅するため、計算量は指数オーダーになりますが、文字列が短い場合は十分に実用的です。

実装例

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

def solve(s):
   res = [0]
   def dfs(s, path=set()):
      if not s:
         res[0] = max(res[0], len(path))
         return
      for i in range(1, len(s)+1):
         x = s[:i]
         if x not in path:
            dfs(s[i:], path|{x})
   dfs(s)
   return res[0]

s = "pqpqrrr"
print(solve(s))

入力

"pqpqrrr"

出力

5