RepeatString
SRM 698 (Google) · 2016-08-27 · by cgy4ever
SRM 698 (Google) · 2016-08-27 · by cgy4ever · Dynamic Programming
Problem Statement
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 aString s.
You want to change s into a square.
You may do the following operations:
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).
You are given a
- 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).
Constraints
- s will contain between 1 and 50 characters, inclusive.
- Each character in s will be a lowercase English letter ('a'-'z').
Examples
0)
"aba" Returns: 1
One of the optimal solutions is to remove the 'b'. This changes the given s into the square "aa".
1)
"adam" Returns: 1
Here, one optimal solution is to change the 'm' to 'd' to get "adad".
2)
"x" Returns: 1
This time one optimal solution is to append another 'x' to get "xx".
3)
"aaabbbaaaccc" Returns: 3
For example, we can change this string into "aaabbbaaabbb". Note that this requires three operations, not one.
4)
"repeatstring" Returns: 6
Submissions are judged against all 134 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class RepeatString with a public method int minimalModify(string s) · 134 test cases · 2 s / 256 MB per case