Skip to main content
Talentd

Minimum Suffix Flips - Solution & Explanation

MediumStringGreedy14 min readAsked at: Amazon, Microsoft, Morgan Stanley +2
Practice this problem

Problem Statement

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.length
  • 1 <= n <= 105
  • target[i] is either '0' or '1'.

Approach Overview

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.

Approach 1: Track Transitions in Target String

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`.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 2: Pattern Matching from Index 0

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), iterating for entire string length.
Space Complexity: O(1), owing to steady-state variable requirement.

Try this approach in the editor →

Approach 3: Greedy

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).

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Track Transitions in Target String

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.

Pattern Matching from Index 0

Time Complexity: O(n), iterating for entire string length.
Space Complexity: O(1), owing to steady-state variable requirement.

Greedy—

Detailed Complexity Analysis

ApproachTimeSpaceWhen 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.

Video Solution

1529. Bulb Switcher IV | Leetcode Medium | Greedy • Chhavi Bansal • 2,076 views views

Watch 6 more video solutions →

Frequently Asked Questions

Is Minimum Suffix Flips easy or hard?
Minimum Suffix Flips is classified as a Medium problem on LeetCode. The implementation is short, but the challenge lies in recognizing the greedy insight that flips correspond to transitions in the target string.
How to solve Minimum Suffix Flips in O(n)?
Iterate through the target string while maintaining the current effective bit after previous flips. If the effective value differs from the target character, increment the flip counter and toggle the state. This greedy strategy ensures each index is processed once, giving O(n) time complexity.
What is the best approach for Minimum Suffix Flips?
The optimal approach is a greedy transition-count method. Traverse the target string and track the current effective bit after previous flips. Whenever the desired bit differs from the current state, perform a flip and toggle the state. This solves the problem in O(n) time and O(1) space.
What data structure is used in Minimum Suffix Flips?
The problem mainly uses string traversal with a greedy strategy. No complex data structures are required. A simple counter and a variable tracking the current flip state are enough to implement the optimal solution.
What is the time complexity of Minimum Suffix Flips?
The optimal solution runs in O(n) time because it scans the target string once. Each character is processed with constant-time checks. The space complexity is O(1) since only a few variables are used to track the current flip state.
Minimum Suffix Flips Python or Java solution approach?
Both Python and Java implementations follow the same logic: iterate through the string, compare the effective bit with the target bit, and increment the flip counter when they differ. The algorithm runs in O(n) time and uses constant extra space.
Is Minimum Suffix Flips asked at Google, Amazon, or Meta interviews?
Greedy string problems like Minimum Suffix Flips appear in interviews at large tech companies including Amazon and Google. The problem tests your ability to recognize patterns in state transitions and avoid unnecessary simulation of operations.

Ready to solve this problem?

Practice Minimum Suffix Flips with our built-in code editor and test cases.

Practice on FleetCode
Previous

Minimum Operations to Make Binary Array Elements Equal to One II