資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究在 Python 中查詢給定字串中具有 k 個唯一字元的最長子字串
假設我們有一個字串，我們必須返回具有恰好 k 個唯一字元的最長可能的子字串，如果有多個最長可能長度的子字串，則返回其中任何一個。
因此，如果輸入類似於 s = "ppqprqtqtqt"，k = 3，則輸出將為 rqtqtqt，因為它的長度為 7。
為了解決這個問題，我們將遵循以下步驟：
N := 26
定義一個函式 is_ok()。這將接收 count 和 k 作為引數。
val := 0
對於 i 從 0 到 N，執行以下操作：
如果 count[i] > 0，則
val := val + 1
當 (k >= val) 時返回 true
從主方法中，執行以下操作：
unique := 0，size := s 的大小
count := 一個大小為 N 的陣列，用 0 填充
對於 i 從 0 到 size，執行以下操作：
如果 s[i] 的計數為 0，則
unique := unique + 1
將 s[i] 的計數增加 1
如果 unique < k，則
沒有這樣的字元，退出
start := 0，end := 0
window_length := 1，window_start := 0
count := 一個大小為 N 的陣列，用 0 填充
將 s[0] 的計數增加 1
對於 i 從 1 到 size，執行以下操作：
將 s[i] 的計數增加 1
end := end + 1
當 is_ok(count, k) 為假時，執行以下操作：
將 s[i] 的計數減少 1
start := start + 1
如果 end-start+1 > window_length，則
window_length := end-start+1
window_start := start
返回 s 的子字串（從索引 window_start 到 window_start + window_length）
示例
讓我們看看以下實現以獲得更好的理解：
N = 26
def is_ok(count, k):
val = 0
for i in range(N):
if count[i] > 0:
val += 1
return (k >= val)
def k_unique_chars(s, k):
unique = 0
size = len(s)
count = [0] * N
for i in range(size):
if count[ord(s[i])-ord('a')] == 0:
unique += 1
count[ord(s[i])-ord('a')] += 1
if unique < k:
return "Not sufficient characters"
start = 0
end = 0
window_length = 1
window_start = 0
count = [0] * len(count)
count[ord(s[0])-ord('a')] += 1
for i in range(1,size):
count[ord(s[i])-ord('a')] += 1
end+=1
while not is_ok(count, k):
count[ord(s[start])-ord('a')] -= 1
start += 1
if end-start+1 > window_length:
window_length = end-start+1
window_start = start
return s[window_start:window_start + window_length]
s = "ppqprqtqtqt"
k = 3
print(k_unique_chars(s, k))輸入
"ppqprqtqtqt", 3
輸出
rqtqtqt
547 次瀏覽
