在Python中查找包含k个不同字符的最长子字符串的长度
假设我们有一个数字k和另一个字符串s,我们必须找到包含至多k个不同字符的最长子字符串的大小。
因此,如果输入为k=3,s=”kolkata”,那么输出将是4,因为有两个包含3个不同字符的最长子字符串,它们是”kolk”和”kata”,长度为4。
为了解决这个问题,我们将遵循以下步骤−
- ans: = 0,left: = 0
-
table: =一个新的映射
-
对于right在0到s大小的范围内,执行以下操作
- table[s[right]]: = 1 +(s[right]如果存在否则0)
-
如果table的大小小于或等于k,则
- ans: = ans和(right-left+1)的最大值
- 否则,
- 当table大小> k时,执行以下操作
-
left_char: = s[left]
-
如果table[left_char]与1相同,则
- 从表中删除第left_char个元素
- 否则,
- table[left_char]: = table[left_char]−1
- left: = left + 1
- 当table大小> k时,执行以下操作
-
返回ans
让我们看下面的实现以获得更好的理解−
更多Python相关文章,请阅读:Python 教程
示例
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