Minimum Number of Changes to Make Binary String Beautiful

medium string greedy blocks of two

Problem

You are given a 0-indexed binary string s of even length. A string is beautiful if it can be split into one or more substrings where each substring has even length and contains only 0's or only 1's. You may change any character to 0 or 1. Return the minimum number of changes to make s beautiful.

Key insight: any even all-same run can be re-cut into pieces of length exactly 2, so it suffices to look at the disjoint blocks s[0..1], s[2..3], … and fix every block whose two characters differ.

Inputs = "1001"

Output2

Blocks "10" and "01" both mismatch, so 2 changes (e.g. make it "1100" = "11|00").

s (binary string, even length)

def minChanges(s):
    changes = 0
    # Walk the string in disjoint blocks of size 2.
    for i in range(0, len(s), 2):
        # A block is fine only if both characters match;
        # if they differ, one flip makes them equal.
        if s[i] != s[i + 1]:
            changes += 1
    return changes

function minChanges(s) {
  let changes = 0;
  // Walk the string in disjoint blocks of size 2.
  for (let i = 0; i < s.length; i += 2) {
    // If the two characters in the block differ,
    // one flip is needed to make them equal.
    if (s[i] !== s[i + 1]) {
      changes++;
    }
  }
  return changes;
}

int minChanges(String s) {
    int changes = 0;
    // Walk the string in disjoint blocks of size 2.
    for (int i = 0; i < s.length(); i += 2) {
        // If the two characters in the block differ,
        // one flip is needed to make them equal.
        if (s.charAt(i) != s.charAt(i + 1)) {
            changes++;
        }
    }
    return changes;
}

int minChanges(string s) {
    int changes = 0;
    // Walk the string in disjoint blocks of size 2.
    for (int i = 0; i < (int)s.size(); i += 2) {
        // If the two characters in the block differ,
        // one flip is needed to make them equal.
        if (s[i] != s[i + 1]) {
            changes++;
        }
    }
    return changes;
}

Explanation

The definition of beautiful allows any partition into even-length single-character substrings. That sounds flexible, but there is a clean simplification: any substring of even length made of the same character can be re-cut into pieces of length exactly 2. So instead of searching over all partitions, we can fix the partition to be the disjoint blocks s[0..1], s[2..3], s[4..5], and so on.

Each such block of length 2 must end up as either "00" or "11". If the block already has two equal characters it costs nothing. If the two characters differ ("01" or "10"), exactly one change turns it into an equal pair — and one change is clearly the minimum for a mismatched pair.

Because the blocks are independent (changing one block never helps another), the global minimum is just the sum of the per-block minimums: count the blocks whose two characters differ.

So the whole algorithm is a single pass with a step of 2: for each index i = 0, 2, 4, … compare s[i] with s[i+1] and add 1 to the answer when they disagree.

Example: s = "1001". Block 0 is "10" (mismatch → +1) and block 1 is "01" (mismatch → +1), giving 2. For s = "0000" both blocks are "00", so the answer is 0.

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