Xâu con hợp lệ dài nhất

Nguồn: CLUE OJ – Chương 15: Ngăn xếp, Hàng đợi Độ khó: Trung bình Ngăn xếp Dãy ngoặc

Đề bài

Cho một xâu có độ dài $L$ ($L \le 10^6$) chỉ chứa các ký tự ( và ). Hãy trả về độ dài dài nhất của xâu con hợp lệ.

Một xâu con hợp lệ trong bài toán này là một đoạn liên tiếp của xâu ban đầu, chỉ chứa các dấu ( và ), thỏa mãn hai điều kiện sau:

Số lượng dấu ( và ) bằng nhau.
Tại mọi vị trí trong đoạn con, số lượng ( từ đầu đến đó luôn $\ge$ số lượng ) (tức là không có dấu ) nào đóng trước khi có dấu ( mở tương ứng).

Ví dụ:

Input	Output	Giải thích
`(()`	2	Xâu con thỏa mãn là `()`
`)()())`	4	Xâu con thỏa mãn là `()()`

Ràng buộc:

20% số test đầu tiên có $L \le 10^2$.
20% số test tiếp theo có $L \le 10^3$.
20% số test tiếp theo có $L \le 10^4$.
20% số test tiếp theo có $L \le 10^5$.
20% số test còn lại không có giới hạn gì thêm.

Ví dụ 1 – input

(()

Ví dụ 1 – output

Ví dụ 2 – input

)()())

Ví dụ 2 – output

Lời mở đầu

Hai điều kiện của đề chính là định nghĩa dãy ngoặc đúng (chỉ một loại ngoặc). Vậy bài hỏi: đoạn con liên tiếp dài nhất là dãy ngoặc đúng. Đề chia 5 subtask rất "đẹp" theo $L$, nên mình sẽ đi đủ 3 nấc: vét cạn $O(L^3)$ → $O(L^2)$ → ngăn xếp $O(L)$, chạy thật cả 3 cách trên bộ test của CLUE để các bạn thấy mỗi cách ăn được tới đâu.

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

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

Bộ test5 subtask Ý tưởngvách ngăn Cách 1O(L³)Cách 2O(L²)Cách 3Ngăn xếp O(L)

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

Test	Độ dài L	Đáp án	Đáp án / L
1 – 20	3 … 100	2 … 94	13% … 94%
21 – 40	1.000	150 … 840	15% … 84%
41 – 60	10.000	2.022 … 8.964	20% … 90%
61 – 80	100.000	11.636 … 89.116	12% … 89%
81 – 100	1.000.000	786.434 … 917.506	79% … 92%

100 test, chia đúng 5 subtask của đề, mỗi subtask 20 test. Từ subtask 2 trở đi, $L$ đúng bằng giới hạn ($10^3, 10^4, 10^5, 10^6$).
Đáp án thường khá dài (cột "Đáp án / L"): ở các test lớn, đoạn hợp lệ dài nhất chiếm phần lớn xâu. Điều này làm các cách "thử đoạn" chạy càng lâu vì phải đi xa mới gặp chỗ hỏng.
Không có test nào đáp án bằng 0 – nhưng code vẫn nên khởi tạo ans = 0 cho trường hợp như )(.

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 $O(L^3)$	Cách 2 $O(L^2)$	Cách 3 $O(L)$
1 (20%)	$L \le 10^2$	1 – 20	20/20	20/20	20/20
2 (20%)	$L \le 10^3$	21 – 40	20/20	20/20	20/20
3 (20%)	$L \le 10^4$	41 – 60	2/20	20/20	20/20
4 (20%)	$L \le 10^5$	61 – 80	0/20	20/20	20/20
5 (20%)	$L \le 10^6$	81 – 100	0/20	0/20	20/20

(Số liệu của bản C++, giới hạn 1 giây/test.)

Ý tưởngNgăn xếp lưu chỉ số, đáy là "vách ngăn"

Ở bài Dãy ngoặc đúng, ta cất ký tự vào ngăn xếp để ghép cặp. Bài này cần độ dài, nên ta cất chỉ số. Ý tưởng then chốt:

Ngăn xếp chỉ số + vách ngăn

Ban đầu đẩy $-1$ vào ngăn xếp: đó là "vách ngăn" – vị trí ngay trước đoạn hợp lệ đang xét.
Gặp ( ở vị trí $i$ → đẩy $i$ vào.
Gặp ) ở vị trí $i$ → lấy đỉnh ra (ghép với ( gần nhất). Sau khi lấy:
- nếu ngăn xếp rỗng: dấu ) này bị thừa, không đoạn hợp lệ nào đi qua được nó → đẩy $i$ vào làm vách ngăn mới;
- ngược lại: đoạn từ sau đỉnh mới tới $i$ là hợp lệ, dài $i - \text{đỉnh}$ → cập nhật đáp án.

Vì sao $i - \text{đỉnh}$ đúng? Đỉnh ngăn xếp sau khi lấy ra là vị trí của ( chưa được ghép gần nhất (hoặc vách ngăn). Mọi ký tự nằm giữa nó và $i$ đều đã ghép cặp xong với nhau → đoạn đó là dãy ngoặc đúng, và không thể kéo dài sang trái hơn được nữa.

Em nhập xâu rồi bấm Tiếp để xem ngăn xếp chỉ số hoạt động, đoạn xanh là đoạn hợp lệ vừa tìm được:

Xâu S:

Ví dụ nhanh:

Cách 1Thử mọi đoạn, kiểm tra từng đoạn – O(L³)

Làm đúng theo định nghĩa của đề: thử mọi đoạn $s[i..j]$, dùng hàm hopLe(l, r) kiểm tra 2 điều kiện bằng một biến đếm bal = (số () − (số )) tính từ đầu đoạn: bal không được âm ở bất kỳ đâu, và cuối đoạn phải bằng 0.

C++▶ Chạy tay từng dòng codeCách 1: thử mọi đoạn độ dài chẵn, mỗi đoạn kiểm tra lại từ đầu – O(L³).

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

Dữ liệu mẫu:

Đoạn hợp lệ luôn có độ dài chẵn, nên j chạy từ i + 1 và tăng 2 mỗi bước – giảm một nửa số đoạn phải thử.
if(bal < 0) return false;: điều kiện 2 của đề – vừa có một ) đóng mà không có ( tương ứng.
Số đoạn cỡ $L^2/4$, mỗi đoạn kiểm tra tốn tới $O(L)$ → $O(L^3)$.

Không gian$O(L)$

Thời gian$O(L^3)$

Kết quả chạy thật: bản C++ đúng 42/100 test (quá 1 giây ở các test 41–50, 53–100), test đúng chạy lâu nhất 0.927s; bản Python đúng 40/100 test (quá thời gian ở các test 41–100), lâu nhất 0.631s.

Vậy Cách 1 ăn trọn subtask 1, 2 ($L \le 1000$); với $L = 10^4$ chỉ lọt được vài test may mắn (đoạn hợp lệ ngắn nên hàm hopLe dừng sớm).

Cách 2Cố định đầu, kéo dài cuối – O(L²)

Cách 1 lãng phí ở chỗ: với cùng điểm đầu $i$, đoạn $s[i..j]$ và $s[i..j+1]$ được kiểm tra lại từ đầu. Thay vào đó, cố định $i$ rồi kéo dài $j$ dần, cập nhật bal chỉ bằng 1 phép cộng/trừ. Hơn nữa, khi bal < 0 thì mọi đoạn bắt đầu từ $i$ dài hơn đều hỏng → break luôn.

C++▶ Chạy tay từng dòng codeCách 2: cố định điểm đầu i, kéo dài j và cập nhật bal – O(L²).

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

Dữ liệu mẫu:

Mỗi khi bal == 0 (và chưa từng âm) thì $s[i..j]$ hợp lệ → cập nhật đáp án.
Trường hợp xấu nhất (ví dụ xâu toàn (, bal không bao giờ âm) vẫn phải đi hết, nên độ phức tạp $O(L^2)$.

Không gian$O(L)$

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

Kết quả chạy thật: bản C++ đúng 80/100 test (quá 1 giây ở các test 81–100), test đúng chạy lâu nhất 0.333s; bản Python đúng 60/100 test (quá thời gian ở các test 61–100), lâu nhất 0.345s.

Bản C++ "lời" hơn dự kiến: qua cả subtask 4 ($L = 10^5$) dù $L^2 = 10^{10}$. Lý do là lệnh break khi bal < 0: trên xâu ngẫu nhiên, từ mỗi điểm đầu $i$ ta thường chỉ đi được một quãng là gặp dấu ) thừa. Nhưng với $L = 10^6$ thì không cứu nổi. Bản Python chậm hơn nên dừng ở subtask 3.

Cách 3Ngăn xếp chỉ số – O(L)

Cài đặt đúng ý tưởng ở trên. Mỗi chỉ số được đẩy vào và lấy ra nhiều nhất một lần nên tổng thời gian là $O(L)$.

C++▶ Chạy tay từng dòng codeCách 3: ngăn xếp lưu chỉ số, đáy là vách ngăn – O(L).

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

Dữ liệu mẫu:

st.push(-1); là vách ngăn ban đầu – nhờ nó mà đoạn hợp lệ bắt đầu từ vị trí 0 vẫn tính được độ dài $i - (-1) = i + 1$.
Khi gặp ) ta pop trước rồi mới kiểm tra rỗng: nếu cái vừa bị lấy ra là vách ngăn thì ngăn xếp rỗng → ) hiện tại thành vách ngăn mới. Ngăn xếp không bao giờ rỗng khi bắt đầu xử lý một ký tự, nên pop luôn an toàn.
Với $L = 10^6$, bản C++ chạy chỉ vài phần trăm giây.

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.014s; bản Python đúng 100/100 test, lâu nhất 0.219s.

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 đoạn, kiểm tra lại	C++	42/100	0.927s	Quá thời gian ở test 41–50, 53–100
	Python	40/100	0.631s	Quá thời gian ở test 41–100
2. Cố định đầu, kéo dài cuối	C++	80/100	0.333s	Quá thời gian ở test 81–100
	Python	60/100	0.345s	Quá thời gian ở test 61–100
3. Ngăn xếp chỉ số	C++	100/100	0.014s	Full điểm
	Python	100/100	0.219s	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 3 full điểm với cả C++ lẫn Python. Điểm mấu chốt của bài: ngăn xếp không chỉ để cất ký tự mà còn cất được chỉ số – từ chỉ số ta tính được độ dài đoạn. Và mẹo đẩy sẵn một "vách ngăn" $-1$ giúp code gọn, khỏi phải xử lý riêng trường hợp đoạn bắt đầu từ đầu xâu.

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 😇

Lập Trình Thuật Toán