TopCoder problem "PalindromeEncoding" used in SRM 324 (Division I Level Three)



Problem Statement

    

The following algorithm can be used to encode a sequence of characters s:

  1. Find any palindrome of even length in s. A palindrome is a string that reads the same forward and backward. If there are no palindromes of even length, go to step 3.
  2. Remove the last half of the selected palindrome from s. For example, if the palindrome is "0110", remove the "10". Go to step 1.
  3. Print the remaining sequence of characters.

Note that the resulting sequence is not necessarily unique since there may be multiple palindromes to choose from in step 1.

Given a String s containing only the digits '0' and '1', return the length of the shortest possible string that can result from applying the above algorithm to s.

 

Definition

    
Class:PalindromeEncoding
Method:getLength
Parameters:String
Returns:int
Method signature:int getLength(String s)
(be sure your method is public)
    
 

Constraints

-s will contain between 1 and 50 characters, inclusive.
-s will contain only the digits '0' and '1'.
 

Examples

0)
    
"0111001"
Returns: 2
First, take the last four digits and remove the "01" to get "01110". Then, select either of the "11"s and remove a "1" to get "0110". Finally, since the entire string is now a palindrome, you can remove the "10" to get "01".
1)
    
"0"
Returns: 1
There is no palindrome of even length in this string, so nothing is changed.
2)
    
"01010111100110101110000001011000101000010111000111"
Returns: 6

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=6766

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10004&pm=6766

Writer:

AdrianKuegel

Testers:

PabloGilberto , brett1479 , Cosmin.ro , Olexiy

Problem categories:

Dynamic Programming, Encryption/Compression, Recursion