problemmediumalgorithmsleetcode-1529leetcode 1529leetcode1529

Minimum Suffix Flips

MediumUpdated: Aug 2, 2025
Practice on:
LeetCode

Problem

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 makes equal totarget.

Examples

Example 1

Input: target = "10111"
Output: 3
Explanation: Initially, s = "00000".
Choose index i = 2: "00 _000_ " -> "00 _111_ "
Choose index i = 0: "_00111_ " -> "_11000_ "
Choose index i = 1: "1 _1000_ " -> "1 _0111_ "
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: "1 _11_ " -> "1 _00_ "
Choose index i = 2: "10 _0_ " -> "10 _1_ "
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 <= 10^5
  • target[i] is either '0' or '1'.

Solution

Method 1 – Greedy Flip Tracking

Intuition

We only need to flip when the current bit differs from the previous bit (starting from '0'). Each change triggers a flip operation.

Approach

  1. Initialize prev = '0', ans = 0.
  2. Iterate through target, if target[i] != prev, increment ans and set prev = target[i].
  3. Return ans.

Code

C++
class Solution {
public:
    int minFlips(string target) {
        int ans = 0;
        char prev = '0';
        for (char c : target) {
            if (c != prev) { ans++; prev = c; }
        }
        return ans;
    }
};
Go
func minFlips(target string) int {
    ans := 0
    prev := byte('0')
    for i := 0; i < len(target); i++ {
        if target[i] != prev { ans++; prev = target[i] }
    }
    return ans
}
Java
class Solution {
    public int minFlips(String target) {
        int ans = 0;
        char prev = '0';
        for (char c : target.toCharArray()) {
            if (c != prev) { ans++; prev = c; }
        }
        return ans;
    }
}
Kotlin
class Solution {
    fun minFlips(target: String): Int {
        var ans = 0
        var prev = '0'
        for (c in target) {
            if (c != prev) { ans++; prev = c }
        }
        return ans
    }
}
Python
class Solution:
    def minFlips(self, target: str) -> int:
        ans = 0
        prev = '0'
        for c in target:
            if c != prev:
                ans += 1
                prev = c
        return ans
Rust
impl Solution {
    pub fn min_flips(target: String) -> i32 {
        let mut ans = 0;
        let mut prev = '0';
        for c in target.chars() {
            if c != prev { ans += 1; prev = c; }
        }
        ans
    }
}
TypeScript
class Solution {
    minFlips(target: string): number {
        let ans = 0, prev = '0';
        for (const c of target) {
            if (c !== prev) { ans++; prev = c; }
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n) — One pass through the string.
  • 🧺 Space complexity: O(1) — Only counters used.

Comments