MakeSquare
SRM 497 · 2010-11-01 · by misof
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
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').
"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.
Submissions are judged against all 48 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class MakeSquare with a public method int minChanges(string S) · 48 test cases · 2 s / 256 MB per case