MakeSquare | Topcoder Archive

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

```
"abcdabgcd"
```
```
Returns: 1
```
One possible way is to delete the letter g.
```
"abcdeabce"
```
```
Returns: 1
```
One possible way is to insert the letter d in front of the last letter e.
```
"abcdeabxde"
```
```
Returns: 1
```
One possible way is to change the letter x to c.
```
"aabcaabc"
```
```
Returns: 0
```
This is already a square.
```
"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.

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.