Given a string containing the only symbols ‘+’ or ‘-‘, how do we find the minimum number of changes to transform it to a chain. A chain of length N is the sequence of alternative + and – symbols.
For example “+-+-+” is a chain of length 5.
Similarly “-+-+-+” is a chain of length 6.
This is a problem from recently concluded Codechef contest. Here is the link to the original problem.
Some examples of input and output are as follows
Input Output
————–
–+ 1
-+- 0
+-+–+ 2
We can solve this problem as follows.
Observation:
Given the length of the sequence N, there are only two possible chains; One starting with – (-+-+….), and the other starting with + (+-+….).
So it is just enough to compare the input string to these two patterns and find the number of changes to make it a chain. Minimum of these two numbers gives us the answer.
For an example consider the input
+–++
Difference with +-+-+ is 2
Difference with -+-+- is 3
So the minimum number of changes to make it a chain is 2.
Here is the C++ code which implements the above.