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

更新于: 2020年11月19日

197 次查看

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告