#CS1087. 最短子序列

最短子序列

题目背景

翻译自 CSES-1087 题。

题目描述

给定一个由字符 A、C、GA、C、GA、C、G 和 T 组成的 DNADNADNA 序列。

你的任务是找到一个最短的 DNADNADNA 序列，它不是原始序列的子序列。

输入格式

输入的唯一一行包含一个长度为 n 的 DNADNADNA 序列。

输出格式

输出一个最短的 DNADNADNA 序列，它不是原始序列的子序列。如果有多个解，你可以输出任意一个。

样例

ACGTACGT

A

说明/提示

1≤n≤106。