Pythonで重複しないサブストリングの最大数を見つけるプログラム

小文字のみの文字列sがあるとすると、次のルールを満たすsの空でない部分文字列の最大数を見つける必要があります

• 部分文字列は重複していません

• 特定の文字chを含むサブストリングには、chのすべての出現箇所も含まれている必要があります。

これらの2つの条件を満たすサブストリングの最大数を見つける必要があります。同じ数の部分文字列を持つそのようなソリューションが複数ある場合は、最小の全長でそれを返します。

したがって、入力がs ="pqstpqqprrr"の場合、条件を満たす可能性のあるすべてのサブ文字列は["pqstpqqprrr"、 "pqstpqqp"であるため、出力は["s"、 "t"、"rrr"]になります。 、"st"、 "s"、 "t"、 "rrr"]

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

• right：=sの右からすべての個々の文字chのインデックス位置のリストをソートします

• 左：=右のすべてのiの文字s[i]のインデックスのリスト

• ：=空のリスト、gen：=空のリスト

• 0から右のサイズまでの範囲のiの場合-1、実行

  • genの最後にs[right[i]]から新しい文字セットを挿入します

  • hasの最後にs[fromindex（left [i] + 1 to right [i] -1]-genの最後の項目）の部分文字列から新しい文字セットを挿入します

  • 範囲サイズが-2から0のjの場合、1ずつ減少します。

    • （has [j] AND last item of gen）がゼロ以外の場合

      • genの最後のアイテム：=genの最後のアイテムまたはgen[j]

      • hasの最後のアイテム：=（hasの最後のアイテムOR has [j]）-genの最後のアイテム

      • has [j]、gen [j]

        を削除します

• res：=新しいリスト、p_right：=-1

• 範囲0からサイズが-1のindの場合、実行します

  • l：=s[i]がgen[ind]

    に存在する場合、左側のすべてのiの要素iのリストの最小値

  • r：=gen [ind]]

    のs[i]の場合、右側のすべてのiの要素iのリストの最大値

  • p_right

    • resの最後にs[インデックスlからr]の部分文字列を挿入します

    • p_right：=r

• 解像度を返す

例

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

def solve(s):
   right = sorted([s.rindex(ch) for ch in set(s)])
   left = [s.index(s[i]) for i in right]
 
   has, gen = [], []
   for i in range(len(right)):
      gen.append(set(s[right[i]]))
      has.append(set(s[left[i] + 1:right[i]]) - gen[-1])

   for j in range(len(has) - 2, -1, -1):
      if (has[-1] & gen[j]) and (has[j] & gen[-1]):
         gen[-1] = gen[-1] | gen[j]
         has[-1] = (has[-1] | has[j]) - gen[-1]
         del has[j], gen[j]

   res, p_right = [], -1
   for ind in range(len(has)):
      l = min([i for i in left if s[i] in gen[ind]])
      r = max([i for i in right if s[i] in gen[ind]])
      if p_right < l:
         res.append(s[l : r + 1])
         p_right = r

   return res

s = "pqstpqqprrr"
print(solve(s))

入力

"pqstpqqprrr"

出力

['s', 't', 'rrr']