### SEH_LENGE_THODA's blog

By SEH_LENGE_THODA, history, 2 months ago, 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 Comments (4)
 » Auto comment: topic has been updated by SEH_LENGE_THODA (previous revision, new revision, compare).
 » Auto comment: topic has been updated by SEH_LENGE_THODA (previous revision, new revision, compare).
 » 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#include #include #define LIMIT (1000*1024) struct item { int next; int id, len; }; int to; struct item t[LIMIT]; int last, count = 0; const char from = { 'A', 'C', 'G', 'T' }; void init( void ) { count = 1; t.id = -1; to['A'] = 0; to['C'] = 1; to['G'] = 2; to['T'] = 3; } void compile( const char *s ) { int i; for( i = 0; s[i] != '\0'; ++i) { int c = to[(int) s[i]], j; for( j = last[c]; j < count; ++j) if( t[j].next[c] == 0 ) t[j].next[c] = count; t[count].id = -1; last[c] = count++; } } char s[LIMIT]; int dfs( int state ) { int i, len; if( t[state].id >= 0 ) return t[state].len; t[state].len = LIMIT; for( i = 0; i < 4; ++i) if( t[state].next[i] == 0 ) { t[state].id = i; t[state].len = 0; return 0; } for( i = 0; i < 4; ++i) if( (len = dfs( t[state].next[i] ))+1 < t[state].len ) t[state].len = len+1, t[state].id = i; return t[state].len; } int main( void ) { int state = 0, len = 0; init(); scanf( "%s", s); compile( s ); dfs( 0 ); for(;;) { s[len++] = from[t[state].id]; if( t[state].len == 0 ) break; state = t[state].next[t[state].id]; } s[len] = '\0'; printf( "%s\n", s); return 0; } 
 »