Minimum Number of Flips to Make the Binary String Alternating

medium string sliding window rotations

Problem

Given a binary string s, you may repeatedly (1) move the first character to the end (a rotation) and (2) flip any single character. Return the minimum number of flips needed to make s alternating (no two adjacent characters equal), where rotations are free.

Because rotations are free, the answer is the cheapest rotation: for each rotation, flips equal the mismatches against the nearer of the two alternating patterns, 0101… or 1010…

Inputs = "111000"

Output2

Rotate twice to get "100011", then flip two characters to reach "101010".

s (binary string)

def minFlips(s):
    n = len(s)
    t = s + s                       # doubled string holds every rotation
    diff = 0                        # mismatches vs pattern "0101..."
    best = n                        # worst case: flip everything once
    l = 0
    for r in range(len(t)):
        if (r & 1) != (ord(t[r]) - 48):   # expected r%2, actual bit
            diff += 1
        if r - l + 1 > n:           # window larger than n: drop left
            if (l & 1) != (ord(t[l]) - 48):
                diff -= 1
            l += 1
        if r - l + 1 == n:          # window is one full rotation
            best = min(best, diff, n - diff)
    return best

function minFlips(s) {
  const n = s.length;
  const t = s + s;                  // doubled string holds every rotation
  let diff = 0;                     // mismatches vs pattern "0101..."
  let best = n;                     // worst case: flip everything once
  let l = 0;
  for (let r = 0; r < t.length; r++) {
    if ((r & 1) !== (t.charCodeAt(r) - 48)) diff++;
    if (r - l + 1 > n) {            // window larger than n: drop left
      if ((l & 1) !== (t.charCodeAt(l) - 48)) diff--;
      l++;
    }
    if (r - l + 1 === n) {          // window is one full rotation
      best = Math.min(best, diff, n - diff);
    }
  }
  return best;
}

int minFlips(String s) {
    int n = s.length();
    String t = s + s;               // doubled string holds every rotation
    int diff = 0;                   // mismatches vs pattern "0101..."
    int best = n;                   // worst case: flip everything once
    int l = 0;
    for (int r = 0; r < t.length(); r++) {
        if ((r & 1) != (t.charAt(r) - '0')) diff++;
        if (r - l + 1 > n) {        // window larger than n: drop left
            if ((l & 1) != (t.charAt(l) - '0')) diff--;
            l++;
        }
        if (r - l + 1 == n) {       // window is one full rotation
            best = Math.min(best, Math.min(diff, n - diff));
        }
    }
    return best;
}

int minFlips(string s) {
    int n = s.size();
    string t = s + s;               // doubled string holds every rotation
    int diff = 0;                   // mismatches vs pattern "0101..."
    int best = n;                   // worst case: flip everything once
    int l = 0;
    for (int r = 0; r < (int)t.size(); r++) {
        if ((r & 1) != (t[r] - '0')) diff++;
        if (r - l + 1 > n) {        // window larger than n: drop left
            if ((l & 1) != (t[l] - '0')) diff--;
            l++;
        }
        if (r - l + 1 == n) {       // window is one full rotation
            best = min(best, min(diff, n - diff));
        }
    }
    return best;
}

Explanation

Flips are the only operation that costs us; rotations are free. So the real question is: across every rotation of s, which one is cheapest to turn into an alternating string?

An alternating string of length n is one of exactly two patterns: 0101… or 1010… They are complements, so if a rotation needs diff flips to match 0101…, it needs n - diff flips to match 1010… We only have to count one of them and take the smaller.

To examine all rotations efficiently we work on the doubled string t = s + s. Every length-n window of t is exactly one rotation of s. Sliding a window of width n across t visits all n rotations in order.

We keep a running count diff of how many characters in the current window disagree with the global pattern 0101… (where index i should hold bit i % 2). When the right edge advances we add a mismatch if the new character disagrees; when the window grows past width n we drop the left character, subtracting its mismatch. The parity comparison uses the absolute index, which stays consistent for the fixed global pattern.

Each time the window is exactly n wide it represents a complete rotation, and we update best = min(best, diff, n - diff). After the slide finishes, best is the minimum flips over all rotations — the answer.

For s = "111000" the cheapest rotation is "100011", which needs 2 flips to become "101010", so the result is 2.

Time: O(n) Space: O(n)