https://binarysearch.com/problems/Removing-Triple-Successive-Duplicates from Google

Thinking process:

Most of the solutions use a smart apprach. Let say if there is a group of 1, like 11111, we should change the inner 1 to 0, like 11011. We shouldn’t change the outter 1 to 0 like 01101 as changing the outter 1 to 0 might result in successive 0 from that side.

For example, if the input is 1100011, there are three 0 in the middle, and we shouldn’t change the outter 0 to 1, otherwise we create another problem, so we can only change the inner 0. Thus, the answer is 1101011. With this strategy, we know that for every group of 1 or 0, we only need to change n/3 “inner” 1 to 0 or 0 to 1 so that we can solve this problem, which leads to a very simple code.

What if we can’t see this pattern?

Here I provide another DP solution, which is basically a brute force solution. Let’s say given any position i in the string, there’s only two choices, 1 or 0. If it’s a 1, there’s only two possible compositions like below.

          i
xxxxxxxxx01
xxxxxxxx011

So, if we define co[i] as the minimum operations for position i being one, and cz[i] as the minimum operations for position i being zero, then

co[i] = (cost of changing s[i] to 1) + min(cz[i-1], cz[i-2]+cost of changing s[i-1] to 1)
cz[i] = (cost of changing s[i] to 0) + min(co[i-1], co[i-2]+cost of changing s[i-1] to 0)

So, we get below code

 1int solve(string s) {
 2    int N = s.size();
 3    if (N == 0) return 0;
 4    int pz, po, ppz, ppo;
 5    for (int i=0; i<N; i++) {
 6        int cz, co;
 7        if (i == 0) {
 8            cz = s[i] != '0';
 9            co = s[i] != '1';
10        } else if (i == 1) {
11            cz = (s[i] != '0') + min(pz, po);
12            co = (s[i] != '1') + min(pz, po);
13        } else {
14            cz = (s[i] != '0') + min(po, ppo + (s[i-1] != '0'));
15            co = (s[i] != '1') + min(pz, ppz + (s[i-1] != '1'));
16        }
17        ppz = pz, ppo = po, pz = cz, po = co;
18    }
19    return min(pz, po);
20}