CSES - Shortest Subsequence | Dãy con ngắn nhất
Xem PDF
Điểm:
1500 (p)
Thời gian:
1.0s
Bộ nhớ:
512M
Input:
bàn phím
Output:
màn hình
Bạn được cho một dãy DNA gồm các kí tự A, C, G và T.
Nhiệm vụ của bạn là tìm dãy DNA ngắn nhất mà không phải là dãy con (có thể thu được bằng cách xóa một số kí tự) của dãy gốc.
Input
- Dòng đầu vào duy nhất chứa một dãy DNA với \(n\) kí tự.
Output
- In dãy DNA ngắn nhất mà không phải là dãy con của dãy gốc. Nếu có một số giải pháp, bạn có thể in bất kì giải pháp nào trong số đó.
Constraints
- \(1 \leq n \leq 10 ^ 6\)
Example
Sample input
ACGTACGT
Sample output
AAA
Bình luận
Đọc đề chả hiểu cái gì
ò tui cx ko hỉu
Đưa ra xâu ngắn nhất chỉ gồm 4 kí tự A C G T, sao cho chúng không phải là xâu con của xâu đã cho
vấn ko hỉu tại sao lại input ra AAA á
Tại vì xâu AAA là một trong những xâu ngắn nhất thỏa mãn điều kiện, xâu AAA không là xâu con của ACGTACGT ấy
nhưng sao lại có 3 chữ AAA vạy chứ trong đè có 2 chữ thôi mà tại sao lại in ra 3 chữ AAA
Bởi vì đề yêu cầu in ra xâu mà không phải là xâu con của xâu cho trước mà