Xóa các chữ cái trùng lặp

Nguồn: CLUE OJ – Cửa sổ trượt + Tham lam Độ khó: Khá Tham lam Ngăn xếp đơn điệu

Đề bài

Cho một xâu $S$ có độ dài $L$ $(L \le 10^6)$ chỉ gồm các chữ cái tiếng Anh in thường. Hãy xóa các chữ cái trùng lặp sao cho kết quả xâu còn lại sau khi xóa chỉ gồm những chữ cái phân biệt và có thứ tự từ điển nhỏ nhất. In ra xâu kết quả thỏa mãn.

Ràng buộc:

• $25\%$ số test đầu tiên có $L \le 20$;
• $25\%$ số test tiếp theo có $L \le 10^3$ và xâu đáp án có độ dài tối đa 7 ký tự;
• $50\%$ số test còn lại không có giới hạn gì thêm.

Ví dụ 1 – input

bcabc

Ví dụ 1 – output

abc

Ví dụ 2 – input

cbacdcbc

Ví dụ 2 – output

acdb

Giải thích: "Xóa các chữ cái trùng lặp" nghĩa là mỗi chữ cái có trong $S$ phải còn lại đúng một lần (không được xóa hết một chữ cái), và ta được chọn giữ lại lần xuất hiện nào. Với bcabc: giữ a ở vị trí 3, b, c ở cuối → abc. Với cbacdcbc: các xâu hợp lệ như bacd, acdb, cadb, … và nhỏ nhất là acdb.

Lời mở đầu

Bài này là một bài tham lam rất "xịn" (trên LeetCode nó tên là Remove Duplicate Letters), lời giải cuối cùng chỉ khoảng 10 dòng với một ngăn xếp, nhưng để hiểu vì sao nó đúng thì phải suy nghĩ một chút. Mình sẽ đi từ vét cạn (subtask 1), qua cách thử hoán vị (subtask 2), rồi mới tới cách tham lam $O(L)$.

Dành cho học viên · Ưu tiênNộp bài trên hệ thống CLUE OJ

Link này chỉ học viên đã tham gia tổ chức mới vào được. Học viên nên ưu tiên nộp ở đây vì sẽ được chấm nhanh hơn.

Nộp bài trên CLUE OJ

Dành cho tất cả mọi ngườiNộp bài trên Codeforces

Bạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì dùng link này nhé. Chưa có tài khoản thì tạo tài khoản rồi đăng nhập nộp bài thử hen.

Nộp bài trên Codeforces

Lộ trình lời giải, bấm vào từng phần để nhảy tới:

Bộ test100 test, 3 subtaskÝ tưởngngăn xếpCách 1tập conCách 2hoán vịCách 3O(L)

Bộ testBộ test chính thức có gì?

Test	Độ dài L	Số chữ cái khác nhau (= độ dài đáp án)
1 – 25	5 … 20	3 … 17
26 – 50	30 … 40	7
51 – 100	30 … 59	16 … 24

• Bộ test có 100 test, chia đúng theo 3 subtask: test 1–25 có $L \le 20$, test 26–50 có $L \le 40$ và đáp án đúng 7 ký tự, test 51–100 có tới 24 chữ cái khác nhau.
• Điều lạ: đề cho $L \le 10^6$ nhưng xâu dài nhất trong bộ test chỉ có 59 ký tự. Dù vậy, như các bạn sẽ thấy, chừng đó đã đủ để các cách vét cạn "chết đứng" vì số trường hợp tăng theo hàm mũ.

Các subtask khớp với bộ test như sau (ô ghi số test đúng của từng cách – chạy thật):

Subtask	Điều kiện	Các test	Cách 1 thử mọi tập con	Cách 2 thử hoán vị	Cách 3 ngăn xếp
1 (25%)	$L \le 20$	1 – 25	25/25	4/25	25/25
2 (25%)	$L \le 10^3$, đáp án $\le 7$ ký tự	26 – 50	0/25	25/25	25/25
3 (50%)	$L \le 10^6$	51 – 100	0/50	0/50	50/50

Ý tưởngChữ nhỏ muốn đứng trước: đẩy chữ lớn ra sau nếu được

Ta xây dựng xâu kết quả từ trái sang phải, đọc lần lượt từng ký tự của $S$, giữ xâu kết quả hiện tại trong một ngăn xếp st. Khi đọc ký tự ch ở vị trí $i$:

1. Nếu ch đã có trong st thì bỏ qua (giữ chỗ cũ của nó).
2. Ngược lại, nhìn đỉnh ngăn xếp: nếu đỉnh lớn hơn ch và chữ ở đỉnh còn xuất hiện ở phía sau vị trí $i$ thì bỏ đỉnh đi (lát nữa sẽ lấy lại nó ở vị trí sau). Lặp lại cho tới khi không bỏ được nữa.
3. Đẩy ch vào ngăn xếp.

Vì sao tham lam này đúng?

Thứ tự từ điển được quyết định bởi ký tự đầu tiên khác nhau. Nếu đỉnh x > ch mà x vẫn còn ở phía sau, thì bỏ x ở đây để ch đứng sớm hơn chắc chắn tạo ra xâu nhỏ hơn – còn x không bị mất vì ta lấy được nó ở lần xuất hiện sau. Nếu x không còn xuất hiện nữa thì bắt buộc phải giữ nó (mỗi chữ phải có mặt đúng 1 lần), và cũng không được bỏ các chữ nằm dưới nó. Vì vậy ngăn xếp luôn là xâu nhỏ nhất có thể với phần đã đọc.

Để biết "còn xuất hiện phía sau không", ta tính trước cuoi[c] = vị trí xuất hiện cuối cùng của chữ c: chữ ở đỉnh còn xuất hiện sau $i$ khi và chỉ khi cuoi[đỉnh] > i.

Em nhập xâu rồi bấm Tiếp để xem ngăn xếp thay đổi thế nào:

Xâu S:

Ví dụ nhanh:

Cách 1Thử mọi cách xóa – O(2^L·L)

Mỗi ký tự của $S$ có 2 lựa chọn: giữ hoặc xóa. Dùng một số nguyên mask $L$ bit: bit $i$ bằng 1 nghĩa là giữ ký tự $s_i$. Với mỗi mask ta ghép xâu t gồm các ký tự được giữ, kiểm tra t không có chữ lặp và có đủ mọi chữ cái của $S$, rồi lấy t nhỏ nhất.

C++▶ Chạy tay từng dòng codeCách 1: thử mọi mask giữ/xóa, lấy xâu hợp lệ nhỏ nhất – O(2^L · L).

Dữ liệu vào (stdin) – sửa thoải máibca

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

Cách 1 rất nhiều bước nên khung này chỉ nhận xâu dài tối đa 4.

1. Tập chữ cái được lưu bằng bit: chữ c ứng với bit 1 << (c - 'a'). canCo là tập chữ của cả xâu $S$, daCo là tập chữ của t.
2. Gặp chữ đã có trong daCo thì t bị lặp → bỏ luôn mask này.
3. mask kiểu long long và 1LL << L: nếu viết 1 << L với $L \ge 32$ sẽ bị tràn số và vòng lặp chạy sai.
4. Có $2^L$ mask, với $L = 20$ là khoảng một triệu – vẫn ổn; nhưng $L = 40$ đã là $10^{12}$.

Không gian$O(L)$

Thời gian$O(2^L \cdot L)$

Kết quả chạy thật: bản C++ đúng 25/100 test (quá thời gian ở các test 26–100), test đúng chạy lâu nhất 0.071s; bản Python đúng 16/100 test (quá thời gian ở các test 4, 7–8, 10, 12, 17–19, 25–100), lâu nhất 0.66s.

Cách 2Thử các hoán vị theo thứ tự từ điển

Nhìn từ phía đáp án: đáp án là một hoán vị của các chữ cái khác nhau trong $S$, và phải là dãy con (không cần liên tiếp) của $S$. Hàm next_permutation sinh các hoán vị theo đúng thứ tự từ điển tăng dần, nên hoán vị đầu tiên là dãy con của $S$ chính là đáp án. Subtask 2 có đáp án tối đa 7 ký tự → nhiều nhất $7! = 5040$ hoán vị, mỗi hoán vị kiểm tra $O(L)$.

C++▶ Chạy tay từng dòng codeCách 2: thử các hoán vị theo thứ tự từ điển, hoán vị đầu tiên là dãy con của s là đáp án.

Dữ liệu vào (stdin) – sửa thoải máibcabc

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. sort rồi unique + erase để lấy các chữ cái phân biệt theo thứ tự tăng dần – đây là hoán vị nhỏ nhất.
2. Hàm laDayCon dùng hai con trỏ: i chạy trên $S$, j chạy trên t; gặp ký tự khớp thì j++. Hết $S$ mà j đi hết t thì t là dãy con.
3. Bản Python dùng mẹo ch in it trên một iterator: mỗi lần in sẽ "ăn" dần $S$ cho tới khi gặp ch, đúng y như hai con trỏ.
4. Với $d$ chữ cái khác nhau, xấu nhất phải thử $d!$ hoán vị: $d = 24$ là khoảng $6 \cdot 10^{23}$.

Không gian$O(L)$

Thời gian$O(d! \cdot L)$, $d$ = số chữ cái khác nhau

Kết quả chạy thật: bản C++ đúng 29/100 test (quá thời gian ở các test 3–12, 14–20, 22–25, 51–100), test đúng chạy lâu nhất 0.828s; bản Python đúng 27/100 test (quá thời gian ở các test 3–25, 51–100), lâu nhất 0.03s.

Để ý: Cách 2 lại thua Cách 1 ở subtask 1 – xâu ngắn nhưng có tới 11–17 chữ cái khác nhau, nên số hoán vị phải thử trước khi gặp đáp án là khổng lồ (trừ vài test may mắn gặp đáp án sớm). Muốn ăn cả 2 subtask đầu thì kết hợp: $L \le 20$ dùng Cách 1, còn lại dùng Cách 2.

Cách 3Tham lam với ngăn xếp – O(L)

Cài đặt đúng ý tưởng ở trên. Dùng luôn một string làm ngăn xếp (back(), push_back(), pop_back()) để cuối cùng in ra được ngay.

C++▶ Chạy tay từng dòng codeCách 3: tham lam với ngăn xếp đơn điệu, mỗi ký tự vào/ra ngăn xếp tối đa 1 lần – O(L).

Dữ liệu vào (stdin) – sửa thoải máicbacdcbc

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. cuoi[c] tính trước bằng một vòng lặp: vị trí sau ghi đè vị trí trước nên cuối cùng còn lại vị trí xuất hiện cuối cùng.
2. trongSt[c] cho biết chữ c đã ở trong ngăn xếp chưa, để bỏ qua trong $O(1)$. Khi pop phải nhớ đặt lại trongSt về false.
3. Mỗi ký tự được đẩy vào và lấy ra khỏi ngăn xếp nhiều nhất một lần → tổng thời gian $O(L)$ dù có vòng while bên trong for.
4. Ngăn xếp luôn tăng dần trừ những chữ "bắt buộc giữ" – đây là dạng ngăn xếp đơn điệu rất hay gặp.

Không gian$O(L)$

Thời gian$O(L)$

Kết quả chạy thật: bản C++ đúng 100/100 test, test đúng chạy lâu nhất 0.007s; bản Python đúng 100/100 test, lâu nhất 0.03s.

Tổng kếtKết quả chạy thật trên bộ test

Cách	Ngôn ngữ	Đúng	Lâu nhất (test đúng)	Ghi chú
1. Thử mọi tập con	C++	25/100	0.071s	Quá thời gian ở test 26–100
	Python	16/100	0.663s	Quá thời gian ở test 4, 7–8, 10, 12, 17–19, 25–100
2. Thử hoán vị	C++	29/100	0.828s	Quá thời gian ở test 3–12, 14–20, 22–25, 51–100
	Python	27/100	0.030s	Quá thời gian ở test 3–25, 51–100
3. Tham lam + ngăn xếp	C++	100/100	0.007s	Full điểm
	Python	100/100	0.033s	Full điểm

Ghi chú của mình: thời gian trong bảng là thời gian CPU đo trên máy của mình (giới hạn 1 giây/test). Cách 1 chỉ qua subtask 1, Cách 2 chủ yếu qua subtask 2; các test còn lại bị quá thời gian dù xâu chỉ dài vài chục ký tự – số trường hợp tăng theo hàm mũ / giai thừa. Cách 3 full điểm và chạy tức thì với cả C++ lẫn Python; với $L = 10^6$ đúng như đề thì nó vẫn chỉ là $O(L)$.

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇