程序查找最长子字符串的长度，该子字符串在Python中包含k个不同的字符

Z时代
2024-01-10
分类：综合

假设我们有一个数字k和另一个字符串s，我们必须找到包含最多k个不同字符的最长子字符串的大小。

因此，如果输入像k = 3 s =“ kolkata”，则输出将为4，因为有两个带有3个不同字符的最长的子字符串，即“ kolk”和“ kata”，其长度为4。

为了解决这个问题，我们将遵循以下步骤-

ans：= 0，左：= 0
表格：=新映射
对于right在0到s − 1的范围内，请执行

当表的大小> k时
table [left_char]：= table [left_char] − 1
从表中删除left_char-th个元素

left_char：= s [左]
如果table [left_char]与1相同，则
除此以外，
左：=左+1
ans：= ans和的最大值（（右-左+ 1）

table [s [right]]：= 1 +（s [right]如果存在，否则为0）
如果表的大小<= k，则
除此以外，

返回ans

让我们看下面的实现以更好地理解-

示例

class Solution:
   def solve(self, k, s):
      ans = 0
      left = 0
      table = {}
      for right in range(0, len(s)):
         table[s[right]] = table.get(s[right], 0) + 1
         if len(table) <= k:
            ans = max(ans, right − left + 1)
         else:
            while len(table) > k:
               left_char = s[left]
               if table[left_char] == 1:
                  table.pop(left_char)
               else:
                  table[left_char] −= 1
               left += 1
      return ans
ob = Solution()
k = 3
s = "kolkata"
print(ob.solve(k, s))