TopCoder problem "MakeSquare" used in SRM 497 (Division II Level Three)



Problem Statement

    

A string is called a square if it is the concatenation of two copies of the same string.

For example, strings abcabc and aaaa are squares, strings aaa, abcab, and defgh are not.

Given a string S, a step is one of the following changes:

  • Changing a single letter in S to any other letter.
  • Erasing a single letter from S.
  • Adding one new letter anywhere into S, including the beginning or the end of S.

For example, if S=abaca, then each of the strings abeca, baca, abafca, and gabaca can be reached from S in a single step. You need at least two steps to reach the string bac, at least four steps to reach the string dafg, and at least five steps to reach the empty string.

You are given a String S. Return the smallest number of steps necessary to change S into a square.

 

Definition

    
Class:MakeSquare
Method:minChanges
Parameters:String
Returns:int
Method signature:int minChanges(String S)
(be sure your method is public)
    
 

Notes

-It is always possible to change S into a square using a finite number of steps.
 

Constraints

-S will contain between 1 and 50 characters, inclusive.
-Each character in S will be a lowercase letter ('a'-'z').
 

Examples

0)
    
"abcdabgcd"
Returns: 1
One possible way is to delete the letter g.
1)
    
"abcdeabce"
Returns: 1
One possible way is to insert the letter d in front of the last letter e.
2)
    
"abcdeabxde"
Returns: 1
One possible way is to change the letter x to c.
3)
    
"aabcaabc"
Returns: 0
This is already a square.
4)
    
"aaaaabaaaaabaaaaa"
Returns: 2
One possible way is to change the second b into an a, and then to insert a b three positions before the end.

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=14426&pm=8681

Writer:

misof

Testers:

PabloGilberto , legakis , Olexiy , ivan_metelsky , Chmel_Tolstiy

Problem categories:

Dynamic Programming, String Manipulation