Find the Minimum Cost to Equalize a Binary String
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
# Find the Minimum Cost to Equalize a Binary String
You are given a 0-indexed binary string `s` of length `n`. You may apply either operation any number of times:
- Choose an index `i` and invert the prefix from `0` through `i`, inclusive, for cost `i + 1`.
- Choose an index `i` and invert the suffix from `i` through `n - 1`, inclusive, for cost `n - i`.
Inverting changes every `0` in the chosen segment to `1` and every `1` to `0`. Return the minimum total cost needed to make all characters equal. Either an all-zero or an all-one final string is acceptable.
### Examples
**Example 1**
```text
Input: s = "11000"
Output: 2
```
Invert the prefix ending at index `1`. The string becomes `"00000"` for cost `2`, which is the minimum.
**Example 2**
```text
Input: s = "10101"
Output: 6
```
One optimal sequence is `10101 -> 00101 -> 11101 -> 11110 -> 11111`. The operations invert the prefix ending at `0`, the prefix ending at `1`, the suffix starting at `3`, and the suffix starting at `4`, with costs `1 + 2 + 2 + 1 = 6`.
### Constraints
- `1 <= s.length == n <= 10^5`.
- Each `s[i]` is either `'0'` or `'1'`.
### Clarifying Questions
- Must the final characters be a particular bit? No; choose whichever equal-bit result has minimum cost.
- Are the segment endpoints inclusive? Yes; both listed operations include index `i`.
- May an arbitrary internal substring be inverted directly? No; each operation must be a prefix or a suffix.
- What if the string is already uniform? The minimum cost is zero.
### C++ Interface
```cpp
class Solution {
public:
long long minimumCost(string s) {
}
};
```
### Reasoning Checkpoints
- Track what an operation changes about adjacent characters.
- Justify a lower bound on the total cost, including interactions between operations.
- Choose an accumulator type that remains safe at the maximum input size.
```hint Adjacent characters
Which adjacent pairs can change from equal to different, or different to equal, when an entire prefix is inverted?
```
Overview: Find the minimum total cost to make a binary string uniform using prefix or suffix inversions, where each operation costs the length of its chosen segment.
