Problem Statement

Given a binary string s of length n, we can perform two types of operations:

Select index i and flip all characters from index 0 to i (inclusive), with cost i + 1. Select index i and flip all characters from index i to n - 1 (inclusive), with cost n - i.

Return the minimum cost to make all characters in the string equal.

Example 1:

Input: s = "0011" Output: 2 Explanation: Perform operation type 2 at index i = 2 to get s = "0000", cost is 2.

Example 2:

Input: s = "010101" Output: 9

Solution Approach

The key insight is to recognize that for any position i where s[i] != s[i+1], we must choose one of two options:

Flip the prefix [0, i] with cost i + 1 Flip the suffix [i+1, n-1] with cost n - i - 1

When we flip either the prefix or suffix, the equality relationship between other adjacent characters remains unchanged. This means each adjacent pair can be considered independently. For each adjacent pair that differs, we simply choose the cheaper operation to make them equal.

A important consideration is that while the string length might be reasonable, the total accumulated cost could exceed integer range, so we need to use long integers for calculations.

Implementation

public long minimumCost(String inputString) {
    long totalCost = 0;
    int length = inputString.length();
    
    for (int pos = 0; pos < length - 1; pos++) {
        if (inputString.charAt(pos) != inputString.charAt(pos + 1)) {
            // Choose the cheaper operation between flipping prefix [0,pos] or suffix [pos+1,n-1]
            int prefixCost = pos + 1;
            int suffixCost = length - pos - 1;
            totalCost += Math.min(prefixCost, suffixCost);
        }
    }
    
    return totalCost;
}

The algorithm iterates through each adjacent pair of characters. When they differ, it calculates the cost of both possible operations and adds the minimum to our running total. This greedy approach works because each decision affects only one adjacent pair while preserving relationships among other pairs.