### PROBLEM LINK:

**Author:** Dmytro Berezin

**Tester:** Pushkar Mishra

**Editorialist:** Florin Chirica

### PROBLEM

You’re given a string of + and - symbols. A string is called a chain if it does not have two or more equal characters. Our target is to convert the given string into a chain. For doing that, you can flip a character (from + to - and vice versa) of the string. Find out minimum number of flips needed.

### QUICK EXPLANATION

We can notice that by fixing the first character, the rest of the chain is also fixed. There are two ways to fix the first character, by putting either + or -. For both of these possibilities, we can find minimum number of flips needed and take minimum of both to get our final answer.

### EXPLANATION

**Fixing first character fixes entire chain**

We can notice that by fixing the first character, the rest of the chain is also fixed.

If the first character is +, the second one *must* be -, the third one *must* be + and so on.

So, the final string will be something like +-+-+- which is a valid chain.

Similarly, we can say the same when the first character of chain is -.

**Computing minimum number of flips needed to convert a string init into a fixed chain fin**

Given two strings init and fin (init is the initial string, fin is the desired chain), the task now becomes to compute number of positions i where init[i] \neq fin[i]. If we find such a position, we’re forced to make a flip. Otherwise, we don’t need any flip.

**Computing the final answer**

There are two possibilities for chain fin given as follows.

- +-+- \dots
- -+-+- \dots

So we can try each one of these. For each case, we can compute the number of differing position between it and the initial array as stated above.

As we have to find overall minimum number of flips needed, we can take minimum of both of these cases.

**Time Complexity**

Since computing the number of differing position between two strings of size n takes O(n) time. We do this for two cases, so the overall complexity is also O(n).

**Subtask 1 Solution**

As length of string s is very small (|s| \leq 10), we can brute-force over all possible flips in s. As each character can be either + or -, there are total 2^n possibilities which will be at max 1024 for the given n.

**Time Complexity**

We are brute-forcing over all possible 2^n strings, for a fixed string we need \mathbb{O}(n) time. So overall time required will \mathbb{O}(2^n * n)