Minimum Suffix Flips: Greedy State Tracking

LeetCode Minimum Suffix Flips (Problem 1529, also known as Bulb Switcher IV) gives you a string target of length n consisting of '0' and '1'. All bulbs start off (all '0'). In one operation, you pick an index i and flip every bulb from index i through index n - 1. Return the minimum number of flips needed to reach the target configuration.

Why this problem matters

This problem distills a powerful greedy pattern: scanning left to right while tracking cumulative state. Instead of simulating every flip, you realize that a single state variable tells you everything about the current configuration from any position onward. Problems involving toggling, prefix XOR, or cumulative parity all rely on this same observation. Once you internalize the "current state" tracking technique, you can apply it to a whole family of flip and toggle problems.

The problem also tests whether you can resist overcomplicating things. It looks like it might need simulation, a stack, or dynamic programming. But the greedy approach is just a single pass with one variable.

The key insight

Think about what happens when you scan the target string from left to right. You maintain a current variable that represents what every unprocessed bulb currently looks like (after all previous flips). Initially, current = '0' because all bulbs are off.

At each position i, compare target[i] to current. If they match, this position is already correct and you move on. If they differ, you must flip at index i, which toggles everything from i onward. But you do not actually need to toggle the array. Since a flip at i affects all positions from i to the end, it simply toggles your current state. So you flip current from '0' to '1' or from '1' to '0' and increment the flip count.

That is the entire algorithm. Every time the target character does not match the current state, you flip.

The solution

def minFlips(target: str) -> int:
    flips = 0
    current = '0'
    for ch in target:
        if ch != current:
            flips += 1
            current = ch
    return flips

The loop scans left to right. At each character, if the target differs from current, we count a flip and toggle current. The final value of flips is the answer.

Why does this work? Each flip at index i toggles everything from i to the end. The key observation is that you never need to go back. Once you have fixed position i, every future flip happens at a later index, which does not affect positions before i. So greedy left-to-right processing is optimal. No flip is wasted, and no earlier position is disturbed.

Visual walkthrough

Let's trace through target = "10111". We start with current = '0' and scan each position.

Three flips are needed: at index 0 (to turn on the suffix), at index 1 (to turn off the suffix starting at 1), and at index 2 (to turn the suffix back on). Positions 3 and 4 already match after the third flip, so no more flips are needed.

Complexity analysis

The algorithm makes a single pass through the string. It uses only two extra variables (flips and current), so the space is constant. This is optimal since you must read every character at least once.

Building blocks

This problem is built on two reusable patterns that appear across many other problems.

1. Left-to-right greedy with forced moves

At each position, the decision is forced: if the current state does not match the target, you must flip. There is no benefit to delaying a flip, because doing so would leave this position wrong and no future flip can fix it without also re-flipping positions you have already handled. This "forced move" argument is the same one that makes greedy correct in problems like Flip String to Monotone Increasing and Minimum Number of K Consecutive Bit Flips. Whenever fixing position i is mandatory and cannot be deferred, greedy left-to-right processing is the right approach.

2. Cumulative state tracking with a toggle

Instead of maintaining an array of current values, you track a single variable that represents the cumulative effect of all flips so far. Each flip toggles this variable. This is the same idea behind prefix XOR, difference arrays, and parity tracking. The pattern appears whenever operations affect a contiguous suffix or prefix and you need to know the net effect at each position.

Edge cases

All zeros target. If the target is "00000", the initial state already matches. No flips are needed. The algorithm returns 0 because current = '0' matches every character.

All ones target. If the target is "11111", a single flip at index 0 sets everything to 1. The algorithm flips once at position 0 and then matches the rest. Answer: 1.

Alternating pattern. A target like "010101" requires a flip at every position. Each character differs from the previous one, so current toggles at every step. The answer equals the length of the string.

Single character. If the target is "0", the answer is 0. If the target is "1", the answer is 1.

Trailing zeros. A target like "11000" requires 2 flips: one at index 0 (flip all on), then one at index 2 (flip the suffix back off). The algorithm catches this because current becomes '1' after the first flip, then needs to toggle back to '0' at index 2.

From understanding to recall

The solution is five lines of code. But can you reproduce it from memory under pressure? The detail that trips people up is knowing exactly what current represents and why toggling it is equivalent to performing a suffix flip.

Here is the mental model to internalize: current is the state that every unprocessed position would show right now. A suffix flip at index i changes all positions from i onward, which is exactly the same as toggling current. You never need to touch an array.

When reviewing this problem, practice explaining two things. First, why greedy works: fixing the leftmost mismatch is forced, not optional, because no later flip can reach it without disturbing earlier positions. Second, why tracking a single variable is sufficient: every suffix flip toggles the state of all remaining positions uniformly, so one variable captures the entire effect.

If you can articulate both of these points without looking at the solution, you own this problem.

Related posts

• Flip String to Monotone Increasing - Another string flip problem where you scan left to right and track state. The greedy "forced move" argument is nearly identical.
• Minimum Number of K Consecutive Bit Flips - A harder flip problem where the window is fixed at size k. The greedy left-to-right approach is the same, but you also need a queue to track overlapping flip effects.
• String Without AAA or BBB - A different flavor of greedy string building. The shared pattern is making a forced local decision at each step that guarantees a globally optimal result.

CodeBricks breaks the minimum suffix flips LeetCode problem into its greedy state tracking building blocks, then drills them independently with spaced repetition. You type the solution from scratch until the pattern is automatic. When a toggle or flip problem shows up in your interview, you do not think about it. You just write it.