Krammer's blog

https://leetcode.com/problems/minimum-number-of-flips-to-make-the-binary-string-alternating/ from Google

Thinking process:

To form an alternating string, we basically have two ways: starting from 0 or starting from 1, like 010101... or 1010101.... So I use array a to record how many flips we need when starting from 0, and b is for starting from 1.

The other operation is that we can rotate the string. The most common way to handle this requirement is to duplicate this string and combine them together. After that, if we use a slide window with the size equal to s.size() to slide in the new string, we can find all the possibilities after rotation.

Here is the code.

 1class Solution {
 2public:
 3    int minFlips(string s) {
 4        int N = s.size();
 5        s += s;
 6        int L = s.size();
 7        vector<int> a(L+1);
 8        vector<int> b(L+1);
 9        int cur = 0;
10        int ans = L;
11        for (int i=0; i<L; i++) {
12            char c = s[i];
13            a[i+1] = a[i], b[i+1] = b[i];
14            if (c-'0' != cur) {
15                a[i+1]++;
16            }
17            if (c-'0' == cur) {
18                b[i+1]++;
19            }
20            if (i >= N-1) {
21                ans = min(ans, min(a[i+1]-a[i+1-N], b[i+1]-b[i+1-N]));
22            }
23            cur ^= 1;
24        }
25        return ans;
26    }
27};

Editorial: LeetCode 1888 Minimum Number of Flips to Make the Binary String Alternating