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

假设我们有一个数字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))

    输入值

    "anewcoffeepot"
    输出结果
    4

    猜你喜欢