Cho chuỗi s chữ thường. Tìm số lượng chuỗi con không rỗng, không chồng lấn tối đa thỏa: nếu chuỗi con chứa ký tự ch thì phải chứa tất cả lần xuất hiện của ch.
Ví dụ: s = "pqstpqqprrr", đầu ra = ["s","t","rrr"]. Các chuỗi con hợp lệ: ["pqstpqqprrr", "pqstpqqp", "st", "s", "t", "rrr"].
Giải pháp
Xác định khoảng [left, right] cho mỗi ký tự, gộp các khoảng giao nhau:
- right := sorted vị trí cuối cùng của mỗi ký tự
- left := vị trí đầu tiên của ký tự tại right[i]
- has, gen := [], []
- Với i từ 0 đến len(right)-1:
- gen.append({s[right[i]]})
- has.append(set(s[left[i]+1:right[i]]) - gen[-1])
- Với j từ len(has)-2 xuống 0: nếu giao nhau, gộp gen[j] vào gen[-1], has[j] vào has[-1], xóa j
- res := [], p_right := -1
- Với ind từ 0 đến len(has)-1:
- l := min left[i] với s[i] trong gen[ind]
- r := max right[i] với s[i] trong gen[ind]
- Nếu p_right < l: res.append(s[l:r+1]); p_right := r
- Trả về res
Ví dụ minh họa
Xem 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']