Minimum Suffix Flips

Minimum Suffix Flips - Problem

String Greedy Medium

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.

Input & Output

Example 1 — Basic Case

$ Input: target = "10111"

› Output: 3

💡 Note: Start with "00000". Flip at index 0 → "11111". Flip at index 1 → "10000". Flip at index 4 → "10001". Continue until we get "10111" with 3 total operations.

Example 2 — All Zeros

$ Input: target = "000"

› Output: 0

💡 Note: Target is already "000" and our string starts as "000", so no operations needed.

Example 3 — All Ones

$ Input: target = "111"

› Output: 1

💡 Note: Start with "000". One flip at index 0 gives us "111", which matches the target.

Constraints

1 ≤ target.length ≤ 10⁵
target[i] is either '0' or '1'

Visualization

Tap to expand

Asked in

G Google 15 f Facebook 12 a Amazon 8

The key insight is that we only need to flip when the current bit doesn't match the target. The optimal approach tracks flips without simulation, achieving O(n) time and O(1) space complexity.

Common Approaches

Approach	Time	Space	Notes
✓ Greedy - One Pass Left to Right	O(n²)	O(n)	Scan from left to right and flip whenever current bit doesn't match target
Brute Force - Try All Combinations	O(n × 2ⁿ)	O(n)	Generate all possible operation sequences and find the shortest one
Optimized - Track Flips Without Simulation	O(n)	O(1)	Count flips without actually modifying the string by tracking cumulative flip effect

Greedy - One Pass Left to Right — Algorithm Steps

Start with s = all zeros
For each position i, check if s[i] matches target[i]
If not, flip from position i to end and increment operation count
Return total operations

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Start with s="000", target="101"

Check & Flip

At each position, flip if current ≠ target

Count Operations

Each flip increments operation counter

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(char* target) {
    int n = strlen(target);
    char current[21];
    for (int i = 0; i < n; i++) {
        current[i] = '0';
    }
    current[n] = '\0';
    int operations = 0;
    
    for (int i = 0; i < n; i++) {
        if (current[i] != target[i]) {
            operations++;
            // Flip from i to end
            for (int j = i; j < n; j++) {
                current[j] = current[j] == '0' ? '1' : '0';
            }
        }
    }
    
    return operations;
}

int main() {
    char target[21];
    fgets(target, sizeof(target), stdin);
    target[strcspn(target, "\n")] = 0;
    int result = solution(target);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

For each position, we might flip all remaining bits, giving n×n operations

⚠ Quadratic Growth

Space Complexity

O(n)

Need to maintain current string state of length n

⚡ Linearithmic Space

28.5K Views

Medium Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Greedy - One Pass Left to Right — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler