Python程式：查詢字元計數至少為k的最長子字串

假設我們有一個字串 s，其中每個字元都是排序的，我們還有一個數字 k，我們需要找到最長的子字串，使得每個字元至少出現 k 次。

所以，如果輸入類似 s = "aabccddeeffghij" k = 2，則輸出將為 8，因為這裡最長的子字串是 "ccddeeff"，其中每個字元至少出現 2 次。

為了解決這個問題，我們將遵循以下步驟：

• 定義一個函式 rc()。它將接收 lst 作為輸入。
• c := 一個包含所有字元及其出現次數的對映。
• acc := 一個新的列表。
• ans := 0。
• valid := True。
• 對於 lst 中的每個 x，執行以下操作：
  • 如果 c[x] < k，則
    • valid := False。
    • ans := ans 和 rc(acc) 的最大值。
    • acc := 一個新的列表。
  • 否則，
    • 將 x 插入到 acc 的末尾。
• 如果 valid 為真，則
  • 返回 acc 的大小。
• 否則，
  • ans := ans 和 rc(acc) 的最大值。
  • 返回 ans。
• 從主方法中，執行以下操作：
• 返回透過將 s 的每個字元轉換為列表而得到的 rc(新列表)。

讓我們看看下面的實現，以便更好地理解：

示例

 即時演示

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

Arnab Chakraborty

更新於: 2020年11月19日

197 次檢視

開啟你的 職業生涯

透過完成課程獲得認證

開始學習