Minimum Suffix Flips

Medium
1219.

Minimum Suffix Flips

Minimum Suffix Flips is a medium coding problem on strings and greedy, asked in Amazon and Google interviews.

A binary string s of length n starts as all zeros. In one operation you pick an index i and flip every bit of s from index i to the end (each 0 becomes 1 and each 1 becomes 0).

Given the binary string target of length n, return the minimum number of operations needed to turn s into target.

Example 1

Input
target = "00110"
Output
2
Explanation
Flip from index 2 (`00111`), then from index 4 (`00110`).

Example 2

Input
target = "101"
Output
3
Explanation
Flip from 0 (`111`), from 1 (`100`), from 2 (`101`).

Example 3

Input
target = "000"
Output
0

Constraints

  • 1 <= target.length <= 10^5
  • target[i] is '0' or '1'
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} target
 * @return {number}
 */
var minFlips = function(target) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Minimum Suffix Flips — Solution in Python, Java & C++

Minimum Suffix Flips solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Minimum Suffix Flips is a medium coding problem on strings and greedy, asked in Amazon and Google interviews.

  • Difficulty: Medium
  • Topics: Strings, Greedy
  • Asked at: Amazon, Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

A binary string s of length n starts as all zeros. In one operation you pick an index i and flip every bit of s from index i to the end (each 0 becomes 1 and each 1 becomes 0).

Given the binary string target of length n, return the minimum number of operations needed to turn s into target.

Example 1

Input: target = "00110"
Output: 2
Explanation: Flip from index 2 (`00111`), then from index 4 (`00110`).

Example 2

Input: target = "101"
Output: 3
Explanation: Flip from 0 (`111`), from 1 (`100`), from 2 (`101`).

Example 3

Input: target = "000"
Output: 0

Constraints

  • 1 <= target.length <= 10^5
  • target[i] is '0' or '1'

Hints for Minimum Suffix Flips

  1. Hint 1

    Work left to right: once a prefix matches, only flips starting later can keep it intact.

  2. Hint 2

    The bit at index i is decided by how many flips started at or before i.

  3. Hint 3

    A flip is needed exactly where target changes value — counting from an imaginary 0 before index 0.

How to solve Minimum Suffix Flips

Scanning left to right, the current bit of s equals the parity of the flips made so far; a new flip is forced exactly when target[i] differs from target[i − 1] (with target[−1] = 0).

Approach

  1. Set prev = '0' and ops = 0.
  2. For each character c of target: if c != prev, increment ops and set prev = c.
  3. Return ops.

Why it works

Flips starting after i never affect index i, so after fixing indices 0…i−1 the bit at i equals the bit at i − 1 (both have seen the same flips) — which matches target[i − 1]. If target[i] differs, a flip starting exactly at i is unavoidable, and it is enough; if they agree, flipping at i would only have to be undone later. Hence every change point costs exactly one operation and nothing else does.

Complexity

  • Time — O(n)
  • Space — O(1)

Pitfalls

  • Forgetting that s starts at 0: a leading 1 in target costs a flip.
  • Simulating the flips literally is O(n²) — too slow for 10^5.
  • Counting the ones instead of the changes between neighbours.

Reference solution

Python

def minFlips(target: str) -> int:
    ops = 0
    prev = "0"
    for c in target:
        if c != prev:
            ops += 1
            prev = c
    return ops

Java

public static int minFlips(String target) {
    int ops = 0;
    char prev = '0';
    for (int i = 0; i < target.length(); i++) {
        char c = target.charAt(i);
        if (c != prev) {
            ops++;
            prev = c;
        }
    }
    return ops;
}

C++

int minFlips(string target) {
    int ops = 0;
    char prev = '0';
    for (char c : target) {
        if (c != prev) {
            ops++;
            prev = c;
        }
    }
    return ops;
}

JavaScript

var minFlips = function(target) {
    var ops = 0, prev = "0";
    for (var i = 0; i < target.length; i++) {
        if (target[i] !== prev) {
            ops++;
            prev = target[i];
        }
    }
    return ops;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Greedy Algorithms