Minimum number of symbols to change to make a chain

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. 
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.

Leave a Reply

Your email address will not be published. Required fields are marked *