Pythonで文字数がk以上の最長の部分文字列の長さを見つけるプログラム

各文字がソートされた文字列sがあり、数値kもあるとすると、すべての文字が少なくともk回出現するように、最長の部分文字列の長さを見つける必要があります。

したがって、入力がs ="aabccddeeffghij" k =2の場合、出力は8になります。これは、ここでの最長の部分文字列が "ccddeeff"であり、すべての文字が少なくとも2回出現するためです。

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

• 関数rc（）を定義します。これには時間がかかります
• c：=すべての文字とその出現を含むマップ
• acc：=新しいリスト
• ans：=0
• 有効：=真
• lstのxごとに、
  • c [x]
  • 有効：=False
  • ans：=ansとrc（acc）の最大値
  • acc：=新しいリスト
• それ以外の場合、
  • accの最後にxを挿入

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

例

from collections import Counter
class Solution:
      def solve(self, s, k):
         def rc(lst):
            c = Counter(lst)
            acc = []
            ans = 0
            valid = True
            for x in lst:
               if c[x] < k:
                  valid = False
                  ans = max(ans, rc(acc))
                  acc = []
               else:
                  acc.append(x)
               if valid:
                  return len(acc)
               else:
                  ans = max(ans, rc(acc))
               return ans
            return rc(list(s))
ob = Solution()
s = "aabccddeeffghij"
k = 2
print(ob.solve(s, k))

入力

"aabccddeeffghij", 2

出力

8