สมมติว่าเรามีสตริงที่เราต้องส่งคืนสตริงย่อยที่ยาวที่สุดเท่าที่จะเป็นไปได้ซึ่งมีอักขระที่ไม่ซ้ำกันจำนวน k ตัว หากมีสตริงย่อยที่มีความยาวมากที่สุดมากกว่าหนึ่งสตริง ให้ส่งคืนสตริงย่อยใดสตริงหนึ่ง
ดังนั้น หากอินพุตเป็น s ="ppqprqtqtqt", k =3 เอาต์พุตจะเป็น rqtqtqt เนื่องจากมีความยาว 7
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
ไม่ :=26
-
กำหนดฟังก์ชัน is_ok() นี่จะนับ k
-
ค่า :=0
-
สำหรับผมอยู่ในช่วง 0 ถึง N ทำ
-
ถ้านับ[i]> 0 แล้ว
-
วาล :=วาล + 1
-
-
-
คืนค่าเป็นจริงเมื่อ (k>=val)
-
จากวิธีหลัก ให้ทำดังนี้ −
-
ไม่ซ้ำกัน :=0, ขนาด :=ขนาดของ s
-
count :=อาร์เรย์ขนาด N เติม 0
-
สำหรับผมอยู่ในช่วง 0 ถึงขนาด ทำ
-
ถ้าจำนวน s[i] เท่ากับ 0 แล้ว
-
ไม่ซ้ำกัน :=ไม่ซ้ำกัน + 1
-
-
เพิ่มจำนวน s[i] ขึ้น 1
-
-
ถ้าเฉพาะ
-
ไม่มีตัวละครและทางออกดังกล่าว
-
-
เริ่มต้น :=0, สิ้นสุด :=0
-
window_length :=1, window_start :=0
-
count :=อาร์เรย์ขนาด N เติม 0
-
เพิ่มจำนวน s[0] ขึ้น 1
-
สำหรับผมอยู่ในช่วง 1 ถึงขนาด ทำ
-
เพิ่มจำนวน s[i] ขึ้น 1
-
end :=end + 1
-
ในขณะที่ is_ok(นับ k) เป็นเท็จ ทำ
-
ลดจำนวน s[i] ลง 1
-
start :=start + 1
-
-
ถ้า end-start+1> window_length แล้ว
-
window_length :=end-start+1
-
window_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
