ECOO '21 P2 - DNA Derren

View as PDF

Submit solution

Points: 3 (partial)
Time limit: 2.0s
Memory limit: 256M

Problem type

One day Derren decided he would do something remarkable with his life. Since Derren is very ambitious, he has decided he wants to memorize his own DNA genome sequence. The only problem is that the human genome is too long to be memorized letter-by-letter.

In order to help him, you offered to write a program to divide his genome into the least number of words. He tells you that each of these words must be distinctly pronounceable. For a word to be considered distinctly pronounceable, the word must either be one letter in length or each pair of two adjacent letters in a word must contain a vowel and a consonant.

Can you write a program to help Derren memorize his DNA genome?

Input Specification

A single line, the DNA sequence that Derren wants to memorize. The length of the line will contain at least 1 character and will not exceed 10^5 characters in length. The line will only consist of the characters A, C, T and G.

For 70\% of the points, the length of the line will not exceed 100 characters in length.

Output Specification

A single line, the input line with spaces inserted in the best positions to help Derren memorize his DNA Sequence.

Sample Input 1


Sample Output 1


Sample Explanation 1

AC is a two letter word containing a vowel and a consonant.

T is a one letter word. It is separated because the pair CT and TG both would lack a vowel.

GAG is one word because the GA and AG pairs both contain a vowel.

There is a space between GAG and CA since the GC pair lacks a vowel.

CA is a two letter word containing a vowel and a consonant.

Sample Input 2


Sample Output 2



  • 0
    imlivin  commented on July 6, 2024, 10:06 p.m.

    I recommend reading the first line of the editorial to understand the problem. Also, a hint if you're stuck:







    look through each letter individually and check the letter before when deciding to add a space or not.

  • 0
    mrap  commented on June 13, 2024, 11:31 p.m.

    While I can code based on the editorial and complete the challenge, I still don't understand how to arrive at the logic presented in the editorial.

  • 2
    Dr_R_Evans  commented on Oct. 20, 2021, 10:37 a.m.

    The explanation for this problem should be clearer. The examples provided give the wrong impression for solving the problem. There should be an provided sample input and output for GAGAGTCGA, to take one example.