文字列をPythonで一意のサブ文字列の最大数に分割することを見つけるプログラム

文字列sがあるとすると、指定された文字列を分割できる一意のサブ文字列の最大数を見つける必要があります。文字列を空でないサブ文字列の任意のリストに分割して、サブ文字列の連結が元の文字列を形成するようにすることができます。ただし、すべてが同じになるように部分文字列を分割する必要があります。

したがって、入力がs ="pqpqrrr"の場合、['p'、'q'、'pq'、'r'、'rr']のように分割できるため、出力は5になります。 ['p'、'q'、'p'、'q'、'r'、'rr']のように分割すると、ここでは'p'と'q'が複数回存在するため、無効になります。

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

• res：=1つの要素のみを含むリスト0
• 関数dfs（）を定義します。これは、新しい空のセットであるs、パスを取ります
• sが空の場合、
  • res [0]：=res[0]の最大値とパスのサイズ
  • 戻る
• 1からsのサイズの範囲のiについては、
  • x：=s[インデックス0からi-1まで]のサブ配列
  • xがパスにない場合は、
    • dfs（sの部分文字列[インデックスiから終了まで]、パスU {x}）
• メインの方法から次のようにします-
• dfs（s）
• return 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