CSES - Shortest Subsequence | Dãy con ngắn nhất

Tác giả:

Dạng bài

Ngôn ngữ cho phép

Assembly, Awk, C, C#, C++, Clang, Cobol, D, ~~Groovy~~, Haskell, JS, Java, Kotlin, Lua, Node JS, OCaml, ObjectiveC, Output, PHP, Pascal, Perl, Prolog, Pypy, Pypy 3, Python, Ruby, Rust, Scala, Scratch, ~~Swift~~

Đ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

Test 1

Input

ACGTACGT

Output

AAA

Bình luận (8)

Tải bình luận...