Min Changes Beautiful Binary LeetCode 2914

LeetCode 2914 Minimum Number of Changes to Make Binary String Beautiful gives you a binary string s of even length. A binary string is called beautiful if it can be partitioned into one or more substrings where each substring has even length and consists of only one distinct character — either all 0s or all 1s. Your goal is to return the minimum number of character changes needed to make the string beautiful.

A change means replacing one character with the other — flipping a 0 to a 1 or a 1 to a 0. Because the string has even length and must be partitioned into even-length all-same substrings, the structure of the problem reduces to something much simpler than it first appears. Understanding the definition carefully reveals the greedy pair-based approach.

The string length n can be up to 100,000, so the solution must be O(n) or better. Fortunately the optimal approach requires only a single pass over the string with constant extra space, making it one of the more elegant medium-difficulty LeetCode problems.

The critical insight is that every beautiful string must have matching characters at every consecutive pair of positions (0,1), (2,3), (4,5), and so on. If any pair has mismatched characters — "01" or "10" — it can never be part of a valid even-length all-same substring without a change. Each such mismatch requires exactly one flip to resolve.

Why pairs of two and not pairs of four or longer? Because any even-length uniform block can always be decomposed into pairs of uniform characters. The pair (s[i], s[i+1]) at even index i is the indivisible unit: if both characters match, they can be part of any larger uniform block; if they mismatch, exactly one must change regardless of what surrounds them.

This observation transforms the problem from "how do I partition the string optimally" into "how many pairs are mismatched" — a much simpler counting problem. Each mismatched pair contributes exactly 1 to the answer, independent of all other pairs.

The algorithm is a single loop over the string stepping by 2. Initialize a counter to 0. For each even index i from 0 to n-2, check whether s[i] equals s[i+1]. If they differ, increment the counter by 1. After the loop, return the counter.

This is a pure greedy approach: fix each broken pair independently. Because pairs do not overlap and each mismatch costs exactly 1 flip to resolve, fixing them independently is globally optimal. There is no case where fixing one pair helps or hurts another.

The time complexity is O(n) with a single pass. The space complexity is O(1) — only the counter variable is needed beyond the input string. There are no edge cases beyond the loop itself: the even-length guarantee ensures every pair is complete.

A beautiful string requires even-length substrings where each consists entirely of the same character. The minimum building block satisfying this definition is a pair of two identical characters: "00" or "11". Any longer even-length uniform block such as "0000" or "111111" is simply a concatenation of such pairs.

If every pair (s[0]s[1]), (s[2]s[3]), (s[4]s[5]), ... is uniform, then any run of consecutive identical pairs can be merged into a single larger uniform block. For example, if pairs are ("11","11","00","00"), you can partition as "1111" + "0000" — a perfectly beautiful string. The pairs do not need to be the actual partition boundaries; they just need to be individually uniform.

Conversely, if any pair is mismatched, no valid partition can avoid splitting it, because any substring containing index i must also contain index i+1 (or start at i+1, leaving index i isolated — which would create an odd-length segment or a segment that must pair with i-1). Making all pairs uniform guarantees a valid partition exists.

Example 1: s = "1001". Pair at (0,1): s[0]="1", s[1]="0" — mismatch, count becomes 1. Pair at (2,3): s[2]="0", s[3]="1" — mismatch, count becomes 2. Answer: 2. We could flip s[1] to "1" and s[3] to "0" giving "1001" → "1100" (beautiful), or many other valid 2-flip solutions.

Example 2: s = "1100". Pair at (0,1): s[0]="1", s[1]="1" — match, count stays 0. Pair at (2,3): s[2]="0", s[3]="0" — match, count stays 0. Answer: 0. The string is already beautiful — it can be partitioned as "11" + "00", both of which are even-length uniform substrings.

Example 3: s = "0110". Pair at (0,1): s[0]="0", s[1]="1" — mismatch, count becomes 1. Pair at (2,3): s[2]="1", s[3]="0" — mismatch, count becomes 2. Answer: 2. Flip s[1] to "0" and s[2] to "0" → "0000", or flip s[1] to "1" and s[3] to "1" → "0111" wait that is not beautiful — flip s[0] to "1" and s[3] to "1" → "1111". Many valid 2-flip solutions exist.

Python solution: def minChanges(s: str) -> int: count = 0; for i in range(0, len(s) - 1, 2): count += s[i] != s[i+1]; return count. This is arguably one of the shortest medium problem solutions on LeetCode — a single loop with a step-2 range, leveraging the fact that Python booleans are integers (True == 1). You can also write it as a generator sum: return sum(s[i] != s[i+1] for i in range(0, len(s), 2)).

Java solution: public int minChanges(String s) { int count = 0; for (int i = 0; i < s.length() - 1; i += 2) { if (s.charAt(i) != s.charAt(i + 1)) count++; } return count; }. The key is i += 2 in the loop increment — stepping by 2 ensures we check pairs at (0,1), (2,3), (4,5) and never overlap. charAt is O(1) in Java for String, so each iteration is constant time.

Both solutions run in O(n) time with O(1) extra space. The approach is textbook greedy: make each local decision (fix this mismatched pair with 1 flip) independently, and the sum of local decisions equals the global optimum. No dynamic programming or backtracking is needed. This problem rewards recognizing the pair structure immediately.

Can Place Flowers (LeetCode 605) is a greedy problem that scans an array and greedily places flowers at valid positions, similar in spirit to how LeetCode 2914 scans pairs and greedily counts mismatches. Both problems reward a single linear scan with a simple local decision rule — no lookahead needed. The "can place" decision for each position is independent, just as the mismatch decision for each pair is independent.

Maximum Odd Binary Number (LeetCode 2864) asks for the lexicographically largest odd binary number you can make by rearranging characters. It belongs to the same greedy-on-binary-strings family: understand the structure of what makes a valid answer, then construct or count it greedily. Like LeetCode 2914, the key insight transforms the problem from apparent complexity into a simple one-pass scan.

String Matching in an Array (LeetCode 1408) rounds out the greedy string family with substring containment checking. Increasing Triplet Subsequence (LeetCode 334) is another greedy-pair-tracking problem where maintaining two thresholds in a single pass yields the answer — the same single-pass constant-space elegance seen in LeetCode 2914. These problems reward recognizing the core invariant that makes the greedy approach work.