Gene Folding

International Cell Processing Company (ICPC) is a world leader in the analysis of genetic sequences. A genetic sequence is a sequence of nucleotides, which in this problem is represented by a string containing only the letters A, C, G, and T in some combination, each letter representing a single nucleotide (Adenine, Cytosine, Guanine, and Thymine, respectively).

One of the key discoveries made by ICPC is that through a process called Genetically Optimized Organic Folding (GOOF), they can take a genetic sequence and transform it into a simpler one, while preserving many of the properties of the sequence that ICPC wants to analyze.

A single application of GOOF works as follows. Find a point between two adjacent nucleotides in the nucleotide sequence, such that the sequence reads the same from that point in both directions, up until the nearer end of the sequence. For instance, in the sequence ATTACC, there are two such points: AT-TACC and ATTAC-C. Then pick one of these points (say, the first one), and fold the genetic sequence at that point, merging the identical nucleotides (so, in this case the AT and TA would become merged, and the resulting sequence would be CCAT or TACC).

Through repeated application of GOOF, a nucleotide can potentially be made much shorter. However, manually searching for the appropriate folding points is very time-consuming. ICPC reached out to you to write a program that would automate the process of finding the folding points and choosing them so as to obtain the shortest possible genetic sequence from a given input sequence.


The input contains a single string $s$ representing the nucleotide sequence to be analyzed. The string consists of characters A, C, G, and T only. The length of $s$ is between $1$ and $4 \cdot 10^6$, inclusive.


Output the smallest possible length of a sequence obtained from the input by applying GOOF zero or more times.

Sample Input 1 Sample Output 1
Sample Input 2 Sample Output 2
CPU Time limit 9 seconds
Memory limit 1024 MB
Difficulty 3.6medium
Statistics Show
License Restricted, used with permission

Please log in to submit a solution to this problem

Log in