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的末尾
如果有效，则
- 返回acc的大小
否则，
- ans：ans和rc(acc)的最大值
- 返回ans
在主方法中，执行以下操作−
返回通过转换s的每个字符而生成的新列表rc()

让我们看看以下实现，以获得更好的理解−

更多Python相关文章，请阅读：Python 教程

示例

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))