Problem

You are given a 0-indexed binary string s of length n on which you can apply two types of operations:

  • Choose an index i and invert all characters from index 0 to index i (both inclusive), with a cost of i + 1
  • Choose an index i and invert all characters from index i to index n - 1 (both inclusive), with a cost of n - i

Return theminimum cost to make all characters of the string equal.

Invert a character means if its value is ‘0’ it becomes ‘1’ and vice-versa.

Examples

Example 1

1
2
3

Input: s = "0011"
Output: 2
Explanation: Apply the second operation with i = 2 to obtain s = "0000" for a cost of 2. It can be shown that 2 is the minimum cost to make all characters equal.

Example 2

1
2
3
4
5
6
7
8

Input: s = "010101"
Output: 9
Explanation: Apply the first operation with i = 2 to obtain s = "101101" for a cost of 3.
Apply the first operation with i = 1 to obtain s = "011101" for a cost of 2. 
Apply the first operation with i = 0 to obtain s = "111101" for a cost of 1. 
Apply the second operation with i = 4 to obtain s = "111110" for a cost of 2.
Apply the second operation with i = 5 to obtain s = "111111" for a cost of 1. 
The total cost to make all characters equal is 9. It can be shown that 9 is the minimum cost to make all characters equal.

Constraints

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

Solution

Method 1 – Greedy Two-Pass

Intuition

To make all characters equal, we can use either prefix or suffix invert operations. The optimal strategy is to find the minimum cost to make all characters ‘0’ or all ‘1’ by considering the cost of flipping at each index from left to right and right to left.

Approach

  1. For both target characters (‘0’ and ‘1’), do:
    • Traverse from left to right, keeping track of the cost to flip all to target using prefix operations.
    • Traverse from right to left, keeping track of the cost to flip all to target using suffix operations.
    • At each index, calculate the cost if we flip at that index and then flip the rest using the other operation.
  2. Return the minimum cost among all possibilities.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
public:
    long long minimumCost(string s) {
        int n = s.size();
        long long ans = LLONG_MAX;
        for (char tgt : {'0', '1'}) {
            long long cost = 0;
            for (int i = 0; i < n; ++i) {
                if (s[i] != tgt) cost += i + 1;
            }
            ans = min(ans, cost);
            cost = 0;
            for (int i = n-1; i >= 0; --i) {
                if (s[i] != tgt) cost += n - i;
            }
            ans = min(ans, cost);
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

func minimumCost(s string) int64 {
    n := len(s)
    ans := int64(1<<62)
    for _, tgt := range []byte{'0', '1'} {
        cost := int64(0)
        for i := 0; i < n; i++ {
            if s[i] != tgt { cost += int64(i+1) }
        }
        if cost < ans { ans = cost }
        cost = 0
        for i := n-1; i >= 0; i-- {
            if s[i] != tgt { cost += int64(n-i) }
        }
        if cost < ans { ans = cost }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    public long minimumCost(String s) {
        int n = s.length();
        long ans = Long.MAX_VALUE;
        for (char tgt : new char[]{'0', '1'}) {
            long cost = 0;
            for (int i = 0; i < n; ++i) {
                if (s.charAt(i) != tgt) cost += i + 1;
            }
            ans = Math.min(ans, cost);
            cost = 0;
            for (int i = n-1; i >= 0; --i) {
                if (s.charAt(i) != tgt) cost += n - i;
            }
            ans = Math.min(ans, cost);
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    fun minimumCost(s: String): Long {
        val n = s.length
        var ans = Long.MAX_VALUE
        for (tgt in listOf('0', '1')) {
            var cost = 0L
            for (i in 0 until n) {
                if (s[i] != tgt) cost += (i+1).toLong()
            }
            ans = minOf(ans, cost)
            cost = 0L
            for (i in n-1 downTo 0) {
                if (s[i] != tgt) cost += (n-i).toLong()
            }
            ans = minOf(ans, cost)
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution:
    def minimumCost(self, s: str) -> int:
        n = len(s)
        ans = float('inf')
        for tgt in '01':
            cost = sum(i+1 for i, c in enumerate(s) if c != tgt)
            ans = min(ans, cost)
            cost = sum(n-i for i, c in enumerate(s) if c != tgt)
            ans = min(ans, cost)
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

impl Solution {
    pub fn minimum_cost(s: String) -> i64 {
        let n = s.len();
        let s = s.as_bytes();
        let mut ans = i64::MAX;
        for &tgt in &[b'0', b'1'] {
            let mut cost = 0;
            for i in 0..n {
                if s[i] != tgt { cost += (i+1) as i64; }
            }
            ans = ans.min(cost);
            cost = 0;
            for i in (0..n).rev() {
                if s[i] != tgt { cost += (n-i) as i64; }
            }
            ans = ans.min(cost);
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    minimumCost(s: string): number {
        const n = s.length;
        let ans = Number.MAX_SAFE_INTEGER;
        for (const tgt of ['0', '1']) {
            let cost = 0;
            for (let i = 0; i < n; ++i) {
                if (s[i] !== tgt) cost += i+1;
            }
            ans = Math.min(ans, cost);
            cost = 0;
            for (let i = n-1; i >= 0; --i) {
                if (s[i] !== tgt) cost += n-i;
            }
            ans = Math.min(ans, cost);
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n) where n is the length of the string, as we scan the string twice for each target.
  • 🧺 Space complexity: O(1).