Minimum Changes To Make Alternating Binary String

easy string counter

Problem

Given a binary string s, return the minimum number of character flips so the string is alternating (no two adjacent equal).

Inputs = "0100"

Output1

Flip the last char to get "0101".

def min_operations(s):
    cnt = sum(1 for i, c in enumerate(s) if int(c) != i % 2)
    return min(cnt, len(s) - cnt)

function minOperations(s) {
  let cnt = 0;
  for (let i = 0; i < s.length; i++) if ((+s[i]) !== i % 2) cnt++;
  return Math.min(cnt, s.length - cnt);
}

class Solution {
    public int minOperations(String s) {
        int cnt = 0;
        for (int i = 0; i < s.length(); i++) if (s.charAt(i) - '0' != i % 2) cnt++;
        return Math.min(cnt, s.length() - cnt);
    }
}

int minOperations(string s) {
    int cnt = 0;
    for (int i = 0; i < (int)s.size(); i++) if (s[i] - '0' != i % 2) cnt++;
    return min(cnt, (int)s.size() - cnt);
}

Explanation

There are only two possible alternating strings of a given length: one that starts with 0 (0101...) and one that starts with 1 (1010...). The answer is the cheaper of matching either one.

Look at the pattern 0101...: at every even index the digit is 0 and at every odd index it is 1 — in other words the expected digit is exactly i % 2. We count how many positions disagree with that pattern and call it cnt.

Those cnt flips turn the string into 0101.... To instead get 1010..., we would flip the other positions, which costs len(s) - cnt. So the minimum is min(cnt, len(s) - cnt).

Example: s = "0100". Comparing to 0101, only the last character differs, so cnt = 1 and len(s) - cnt = 3. The answer is min(1, 3) = 1.

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