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.