Member-only story
An Edit distance coding problem
I got this problem from a Single Round Match (SRM) of Topcoder platform. Here is the problem link.
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.
