You are given a 0-indexed binary string target of length n. You have another binary string s of length n that is initially set to all zeros. You want to make s equal to target.
In one operation, you can pick an index i where 0 <= i < n and flip all bits in the inclusive range [i, n - 1]. Flip means changing '0' to '1' and '1' to '0'.
Return the minimum number of operations needed to make s equal to target.
Example 1:
Input: target = "10111" Output: 3 Explanation: Initially, s = "00000". Choose index i = 2: "00000" -> "00111" Choose index i = 0: "00111" -> "11000" Choose index i = 1: "11000" -> "10111" We need at least 3 flip operations to form target.
Example 2:
Input: target = "101" Output: 3 Explanation: Initially, s = "000". Choose index i = 0: "000" -> "111" Choose index i = 1: "111" -> "100" Choose index i = 2: "100" -> "101" We need at least 3 flip operations to form target.
Example 3:
Input: target = "00000" Output: 0 Explanation: We do not need any operations since the initial s already equals target.
Constraints:
n == target.length1 <= n <= 105target[i] is either '0' or '1'.Problem Overview: You start with a binary string of all 0s and want to transform it into a target binary string. In one operation, you can flip every bit from an index i to the end of the string (a suffix flip). The task is to compute the minimum number of such flips needed to match the target.
Approach 1: Track Transitions in Target String (Greedy) (Time: O(n), Space: O(1))
The key observation is that a flip only matters when the desired bit changes relative to the current effective state. Start with the assumption that the string is all 0s. As you iterate through the target string, track whether the current state matches the desired character. Every time the desired bit differs from the current effective value, you must perform a suffix flip starting at that index. After a flip, the effective value toggles for the rest of the scan. This reduces the problem to counting transitions where the expected bit differs from the actual target bit. The algorithm performs a single pass through the string while applying a greedy decision at each position.
Approach 2: Pattern Matching from Index 0 (Simulation) (Time: O(n), Space: O(1))
Another way to think about the process is by simulating the flips logically without modifying the string. Maintain a variable representing the current flipped state (0 or 1). Iterate from index 0 to n-1. If the effective bit after considering previous flips differs from the target bit, perform a new flip and toggle the state variable. This effectively simulates applying the suffix flip while keeping the algorithm linear. Instead of physically flipping characters, you just track whether the sequence has been flipped an odd or even number of times so far.
Both approaches rely on the same core insight: the only moments that matter are when the required bit differs from the current effective value. Once a flip happens, the state of all remaining characters is inverted, so the algorithm simply keeps track of that inversion logically.
Recommended for interviews: The transition-count greedy approach is what most interviewers expect. It demonstrates that you recognized the flipping pattern and reduced the problem to counting state changes instead of simulating expensive operations. Explaining the reasoning behind why transitions correspond to flips shows strong understanding of greedy decision making on a string traversal.
Whenever the current bit in `target` is different from the last established state of a similar position of the string `s`, a move (flip) must be made. Start with `s` as all zeros, which initially is '000...0'. As you iterate through `target`, every time a current bit is different from the last flip to match target, a new operation is needed.
This C solution uses a variable `current` to track the expected character of the string `s` that originally starts with 0s. It counts each time a transition between '0' and '1' occurs in `target`.
Time Complexity: O(n), where n is the length of the target string.
Space Complexity: O(1); only a fixed amount of memory is used.
Directly compare the initial `s` state to `target`, beginning with the simplest match from index 0 and capturing changes between segments entirely when flipping results in mismatch. The initial states switch whenever they are inconsistent with the target.
This C technique uses straightforward string index comparison between initialized '0' and `target` indices, emphasizing segment mismatching and flip counting.
Time Complexity: O(n), iterating for entire string length.
Space Complexity: O(1), owing to steady-state variable requirement.
We traverse the string target from left to right, using a variable ans to record the number of flips. When we reach index i, if the parity of the current flip count ans is different from target[i], we need to perform a flip operation at index i and increment ans by 1.
The time complexity is O(n), where n is the length of the string. The space complexity is O(1).
| Approach | Complexity |
|---|---|
| Track Transitions in Target String | Time Complexity: O(n), where n is the length of the target string. |
| Pattern Matching from Index 0 | Time Complexity: O(n), iterating for entire string length. |
| Greedy | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Track Transitions in Target String (Greedy) | O(n) | O(1) | Best general solution. Counts transitions to determine flips without simulation. |
| Pattern Matching from Index 0 (Flip Simulation) | O(n) | O(1) | Useful when explaining the logic step‑by‑step by tracking the current flipped state. |
1529. Bulb Switcher IV | Leetcode Medium | Greedy • Chhavi Bansal • 2,041 views views
Watch 6 more video solutions →Practice Minimum Suffix Flips with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor