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.