Giả sử chúng ta có một chuỗi s chỉ có các chữ cái viết thường, chúng ta phải tìm số chuỗi con không rỗng tối đa của s đáp ứng các quy tắc sau
-
Các chuỗi con không chồng chéo
-
Một chuỗi con chứa một ký tự cụ thể ch cũng phải chứa tất cả các lần xuất hiện của ch.
Chúng ta phải tìm số chuỗi con tối đa thỏa mãn hai điều kiện này. Nếu có nhiều hơn một giải pháp như vậy với cùng số chuỗi con, thì trả về giá trị đó với tổng độ dài tối thiểu.
Vì vậy, nếu đầu vào là s ="pqstpqqprrr", thì đầu ra sẽ là ["s", "t", "rrr"] vì tất cả các chuỗi con có thể đáp ứng các điều kiện là ["pqstpqqprrr", "pqstpqqp" , "st", "s", "t", "rrr"]
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
right:=sắp xếp danh sách vị trí chỉ mục của tất cả các ký tự riêng lẻ ch từ bên phải của s
-
left:=danh sách các chỉ số của các ký tự s [i] cho tất cả các ký tự tôi ở bên phải
-
có:=danh sách trống, gen:=danh sách trống
-
đối với tôi trong phạm vi từ 0 đến kích thước của bên phải - 1, thực hiện
-
chèn một nhóm ký tự mới từ s [right [i]] vào cuối gen
-
chèn một tập hợp ký tự mới từ chuỗi con của s [từ chỉ mục (trái [i] + 1 sang phải [i] -1] - mục cuối cùng của gen) vào cuối có
-
đối với j trong phạm vi kích thước có - 2 đến 0, giảm 1, làm
-
nếu (mục cuối cùng của gen AND [j]) và (có [j] VÀ mục cuối cùng của gen) khác 0, thì
-
item cuối cùng của gen:=item cuối cùng của gen OR gen [j]
-
mục cuối cùng của có:=(mục cuối cùng của có HOẶC có [j]) - mục cuối cùng của gen
-
remove has [j], gen [j]
-
-
-
-
res:=một danh sách mới, p_right:=-1
-
cho ind trong phạm vi 0 đến kích thước của has - 1, do
-
l:=tối thiểu của danh sách các phần tử i cho tất cả các phần tử i ở bên trái nếu s [i] có mặt trong gen [ind]
-
r:=tối đa danh sách các phần tử thứ i cho tất cả các phần tử tôi đúng nếu s [i] trong gen [ind]]
-
nếu p_right
-
chèn chuỗi con của s [từ chỉ mục l đến r] vào cuối res
-
p_right:=r
-
-
-
trả lại res
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn
def solve(s):
right = sorted([s.rindex(ch) for ch in set(s)])
left = [s.index(s[i]) for i in right]
has, gen = [], []
for i in range(len(right)):
gen.append(set(s[right[i]]))
has.append(set(s[left[i] + 1:right[i]]) - gen[-1])
for j in range(len(has) - 2, -1, -1):
if (has[-1] & gen[j]) and (has[j] & gen[-1]):
gen[-1] = gen[-1] | gen[j]
has[-1] = (has[-1] | has[j]) - gen[-1]
del has[j], gen[j]
res, p_right = [], -1
for ind in range(len(has)):
l = min([i for i in left if s[i] in gen[ind]])
r = max([i for i in right if s[i] in gen[ind]])
if p_right < l:
res.append(s[l : r + 1])
p_right = r
return res
s = "pqstpqqprrr"
print(solve(s)) Đầu vào
"pqstpqqprrr"
Đầu ra
['s', 't', 'rrr']