SEH_LENGE_THODA's blog

By SEH_LENGE_THODA, history, 2 months ago, In English

Can anyone suggest me how to solve this problem(https://cses.fi/problemset/task/1087)

You are given a DNA sequence consisting of characters A, C, G, and T.

Your task is to find the shortest DNA sequence that is not a subsequence of the original sequence.

Input

The only input line contains a DNA sequence with n characters.

Output

Print the shortest DNA sequence that is not a subsequence of the original sequence. If there are several solutions, you may print any of them.

Constraints 1≤n≤1e6 Example

Input: ACGTACGT

Output: AAA

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by SEH_LENGE_THODA (previous revision, new revision, compare).

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by SEH_LENGE_THODA (previous revision, new revision, compare).

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

You can construct a trie containing any subsequence of the original string in $$$O(n)$$$. This trie is a DAG in reality so you can apply DP to find the requested string.

Code