資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究Python程式：查詢包含k個不同字元的最長子字串
假設我們有一個數字k和另一個字串s，我們需要找到包含最多k個不同字元的最長子字串的長度。
因此，如果輸入類似於k = 3 s = "kolkata"，則輸出將是4，因為有兩個最長子字串包含3個不同的字元，它們是“kolk”和“kata”，長度為4。
為了解決這個問題，我們將遵循以下步驟：
ans := 0，left := 0
table := 一個新的對映
對於right從0到s的長度-1，執行：
table[s[right]] := 1 + (s[right]如果存在，否則為0)
如果table的大小 <= k，則：
ans := ans和(right - left + 1)中的最大值
否則：
當table的大小 > k時，執行：
left_char := s[left]
如果table[left_char]等於1，則：
從table中刪除left_char處的元素
否則：
table[left_char] := table[left_char] - 1
left := left + 1
返回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
更新於: 2020年12月15日
630 次瀏覽
廣告