Cho chuỗi s và số k (chia hết độ dài n). Chia s thành n/k đoạn con độ dài k. Từ mỗi đoạn, loại bỏ ký tự trùng lặp (giữ thứ tự xuất hiện đầu tiên) tạo thành chuỗi u_i.
Ví dụ: s = "MMPQMMMRM", k = 3 → các đoạn: "MMP", "QMM", "MRM" → kết quả ["MP", "QM", "MR"].
Thuật toán
- Duyệt chuỗi, dùng
sethoặcdicttheo dõi ký tự đã thấy trong đoạn hiện tại. - Khi chuyển đoạn mới (index chia hết cho
k), reset bộ theo dõi và lưu kết quả đoạn trước.
Ví dụ mã nguồn
def solve(s, k):
i = 0
ret = []
mp, to_print = {}, ""
while i < len(s):
if i % k == 0 and i != 0:
ret.append(to_print)
mp, to_print = {}, ""
if s[i] not in mp:
mp[s[i]] = 0
to_print += s[i]
i += 1
ret.append(to_print)
return ret
s = "MMPQMMMRM"
k = 3
print(solve(s, k)) # ['MP', 'QM', 'MR']
Đầu vào / Đầu ra
Input: "MMPQMMMRM", 3
Output: ['MP', 'QM', 'MR']