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

1
2
3
4
5
6
7
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

1
2
3
4
5
6
7
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

1
2
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
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;
    }
};
1
2
3
4
5
6
7
8
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
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
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;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
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
    }
}
1
2
3
4
5
6
7
8
9
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
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
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
    }
}
1
2
3
4
5
6
7
8
9
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.