234. Number of Flips to Make a Binary String Alternating

Given a binary string s, find the minimum number of characters you must flip (change a '0' to '1' or a '1' to '0') so that the resulting string alternates, meaning no two adjacent characters are equal.

Input: The input is a single line containing a binary string s of '0' and '1' characters. Output: Print a single integer - the minimum number of flips needed to make s alternating.

1 <= |s| <= 10^5

There are exactly two possible 'ground truth' alternating targets for any string length - recognizing that the whole solution space collapses to just comparing against these two fixed patterns is the entire key insight.

Find the fewest character flips needed to make a string of 0s and 1s alternate perfectly, with no two neighboring characters the same. Brute force: Try every possible sequence of flips directly (which positions to flip) and check if the result is alternating - this is exponential in the number of possible flip combinations, wildly impractical. Optimised: Since there are only ever TWO possible target alternating patterns for any given length, computing the mismatch count against each in a single pass (and even noticing the two counts always sum to the string's length, so computing one gives you the other for free) directly gives the minimum, with no need to search over flip combinations at all.

Notice the two mismatch counts are complementary: every position mismatches exactly one of the two patterns and matches the other, so the count of flips needed for the 'starts with 1' pattern is always n minus the count needed for the 'starts with 0' pattern. This means only one counter needs to be computed in a single pass (count mismatches against the 'starts with 0' pattern), and the answer is simply the minimum of that count and n minus that count, cutting the work per index in half. Time: O(n) Space: O(1)

Build the two candidate alternating strings explicitly - one starting with '0' and one starting with '1' - then compare each candidate to s character by character, counting mismatches, and report the smaller of the two counts. This is correct since any alternating string of the given length must be one of exactly these two patterns, but materializing both full strings wastes memory that isn't needed. Time: O(n) Space: O(n)

Walk through s once, and at each index compare the actual character to what the 'starts with 0' pattern expects (based on whether the index is even or odd) and separately to what the 'starts with 1' pattern expects, incrementing two running mismatch counters as you go without ever building the target strings. At the end, the answer is the smaller of the two counters, avoiding the O(n) extra space used to store full candidate strings. Time: O(n) Space: O(1)

1. Notice there are only ever TWO possible valid alternating patterns for a given length: one starting with '0' (0101...) and one starting with '1' (1010...). 2. For each of the two target patterns, count how many positions of the original string disagree with it. 3. The answer is the SMALLER of these two counts - flipping only the disagreeing positions turns the string into that target.

Time: O(n) - a single pass comparing against one target pattern (the other's count follows immediately by subtraction from the length). Space: O(1) - just a couple of counters, no extra pattern string needs to be built.

s of length 1 (already alternating, 0 flips); s already alternating (answer 0); s up to 10^5 characters for performance.

Be ready to point out the elegant shortcut that the two mismatch counts always sum to the string's length - so you technically only ever need to compute ONE of them directly, then derive the other by subtraction.