두 번 또는 한 번 timer 2s memory 1024MB

영문 대문자로 이루어진 문자열이 주어진다. 당신은 문자열의 문자들 중 임의의 개수를(전부일 수도 있고 하나도 아닐 수도 있음) 하이라이트할 수 있다. 하이라이트된 문자들은 서로 연속일 필요가 없다. 그 다음 왼쪽에서 오른쪽으로 문자를 처리하여 새 문자열을 만든다. 하이라이트되지 않은 문자는 새 문자열에 한 번 붙이고, 하이라이트된 문자는 새 문자열에 두 번 붙인다.

예를 들어 초기 문자열이 HELLOWORLD라면, H, 첫 번째와 마지막 L, 그리고 마지막 O를 하이라이트하여 다음처럼 만들 수 있다:
HELLOWORLD \Rightarrow HHELLLOWOORLLD. 마찬가지로 아무 것도 하이라이트하지 않으면 HELLOWORLD가 되고, 모든 문자를 하이라이트하면 HHEELLLLOOWWOORRLLDD가 된다. 같은 문자라도 등장 위치마다 독립적으로 하이라이트할 수 있다는 점에 유의하라.

하이라이트 선택에 따라 이 과정으로 만들 수 있는 문자열은 여러 개가 된다. 그중 사전순(lexicographical order)으로 가장 앞서는 문자열을 출력하라.

참고: 서로 다른 두 문자열 s, t에 대해, s가 t의 접두사(prefix)이거나, 두 문자열이 처음으로 다른 위치에서 s의 문자가 t의 문자보다 알파벳 순서로 앞서면, s는 사전순으로 t보다 앞선다. 예를 들어 다음 문자열들은 사전순으로 정렬되어 있다: CODE, HELLO, HI, HIM, HOME, JAM.