RepeatString | Topcoder Archive

Problem Statement

A string S is called a square if there is some string T such that S = T + T. For example, the strings "", aabaab" and "xxxx" are squares, but "a", "aabb" and "aabbaa" are not.

You are given a String s. You want to change s into a square. You may do the following operations:

Insert a new character anywhere into the string (including its beginning and end).
Remove a single character.
Replace a single character by another character.

Please compute and return the smallest number of operations needed to change the given s into a square. Note that this is always possible: for example, you can remove all characters (one at a time).

Definition

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

Constraints

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

Examples

```
"aba"
```
```
Returns: 1
```
One of the optimal solutions is to remove the 'b'. This changes the given s into the square "aa".
```
"adam"
```
```
Returns: 1
```
Here, one optimal solution is to change the 'm' to 'd' to get "adad".
```
"x"
```
```
Returns: 1
```
This time one optimal solution is to append another 'x' to get "xx".
```
"aaabbbaaaccc"
```
```
Returns: 3
```
For example, we can change this string into "aaabbbaaabbb". Note that this requires three operations, not one.
```
"repeatstring"
```
```
Returns: 6
```
```
"aaaaaaaaaaaaaaaaaaaa"
```
```
Returns: 0
```

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.