Giả sử chúng ta có hai chuỗi s và t, chúng ta phải tìm kích thước của một chuỗi con nhỏ nhất tính bằng s chứa tất cả các ký tự của t. Nếu không có chuỗi con nào như vậy tồn tại thì trả về -1.
Vì vậy, nếu đầu vào giống như s ="thegrumpywizardmakes" t ="aw", thì đầu ra sẽ là 10, vì chuỗi con ngắn nhất có chứa "thức" là "wizardmake" (độ dài 10).
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
counter:=tần số của mỗi ký tự trong b
-
bắt đầu:=0
-
min_subs:=inf
-
rem:=số lượng các ký tự riêng biệt trong b
-
cuối cùng trong phạm vi 0 đến kích thước của a, do
-
hiện tại:=a [end]
-
nếu dòng điện trong bộ đếm, thì
-
bộ đếm [hiện tại]:=bộ đếm [hiện tại] - 1
-
nếu bộ đếm [hiện tại] giống 0, thì
-
rem:=rem - 1
-
-
-
trong khi rem giống 0, làm
-
trước_char:=a [bắt đầu]
-
nếu pres_char trong bộ đếm, thì
-
bộ đếm [pres_char]:=bộ đếm [pres_char] + 1
-
nếu bộ đếm [pres_char]> 0, thì
-
rem:=rem + 1
-
-
-
min_subs:=tối thiểu min_subs và (end - start + 1)
-
start:=start + 1
-
-
-
trả về min_subs khi min_subs không phải là -1
Ví dụ (Python)
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
class Solution:
def solve(self, a, b):
counter = {}
for char in b:
counter[char] = counter.get(char, 0) + 1
start = 0
min_subs = float("inf")
rem = len(counter)
for end in range(len(a)):
current = a[end]
if current in counter:
counter[current] -= 1
if counter[current] == 0:
rem -= 1
while rem == 0:
prev_char = a[start]
if prev_char in counter:
counter[prev_char] += 1
if counter[prev_char] > 0:
rem += 1
min_subs = min(min_subs, end - start + 1)
start += 1
return min_subs if min_subs != float("inf") else -1
ob = Solution()
s = "thegrumpywizardmakes"
t = "wake"
print(ob.solve(s, t)) Đầu vào
"thegrumpywizardmakes", "wake"
Đầu ra
2