Minimum Cost to Make All Characters Equal

Minimum Cost to Make All Characters Equal - 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 the minimum cost to make all characters of the string equal.

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

Input & Output

Example 1 — Basic Case

$ Input: s = "0011"

› Output: 1

💡 Note: There's one transition at position 1 (0→1). We can fix this with a right operation at index 2 with cost n-i = 4-2 = 2, or left operation at index 1 with cost i+1 = 2. Actually, the optimal is right operation at index 2 costing 2, but we can do better with right operation at index 3 costing 1 to make all 0s.

Example 2 — All Same

$ Input: s = "1111"

› Output: 0

💡 Note: All characters are already equal, so no operations needed. Cost = 0.

Example 3 — Multiple Transitions

$ Input: s = "010"

› Output: 2

💡 Note: Two transitions: at positions 0 (0→1) and 1 (1→0). For each transition, we choose the cheaper operation. Total cost = min(1,2) + min(2,1) = 1 + 1 = 2.

Constraints

1 ≤ s.length ≤ 10⁵
s consists only of '0' and '1'

Visualization

Tap to expand

Understanding the Visualization

Input

Binary string with mixed 0s and 1s

Find Transitions

Identify positions where adjacent characters differ

Choose Operations

For each transition, pick cheaper flip operation (left or right)

Key Takeaway

🎯 Key Insight: Only transition points between different characters matter - fix each with the cheaper operation

Asked in

G Google 25 f Meta 18 a Amazon 15

The key insight is that we only need to fix transition points where adjacent characters differ. For each transition, we choose the cheaper of two operations: flipping left (cost i+1) or flipping right (cost n-i). The optimal greedy approach runs in O(n) time with O(1) space.

Common Approaches

Approach	Time	Space	Notes
✓ Try All Possible Operations	O(2^n)	O(n)	Try all possible sequences of operations to find minimum cost
Greedy Two-Pass Solution	O(n)	O(1)	Calculate cost to make all 0s and all 1s separately, take minimum

Try All Possible Operations — Algorithm Steps

Generate all possible operation sequences
Simulate each sequence and calculate cost
Return minimum cost found

Visualization

Tap to expand

Step-by-Step Walkthrough

Initial State

Start with original binary string

Try Operations

Recursively try all left and right flip operations

Track Minimum

Keep track of minimum cost when all characters become equal

Code -

solution.c — C

#include <stdio.h>
#include <string.h>
#include <limits.h>

int minCost = INT_MAX;

void backtrack(char* currentS, int cost, int n) {
    // Check if all characters are equal
    char first = currentS[0];
    int allEqual = 1;
    for (int i = 0; i < n; i++) {
        if (currentS[i] != first) {
            allEqual = 0;
            break;
        }
    }
    
    if (allEqual) {
        if (cost < minCost) {
            minCost = cost;
        }
        return;
    }
    
    if (cost >= minCost) return;
    
    // Try left operations
    for (int i = 0; i < n; i++) {
        char newS[1001];
        strcpy(newS, currentS);
        for (int j = 0; j <= i; j++) {
            newS[j] = newS[j] == '0' ? '1' : '0';
        }
        backtrack(newS, cost + i + 1, n);
    }
    
    // Try right operations
    for (int i = 0; i < n; i++) {
        char newS[1001];
        strcpy(newS, currentS);
        for (int j = i; j < n; j++) {
            newS[j] = newS[j] == '0' ? '1' : '0';
        }
        backtrack(newS, cost + n - i, n);
    }
}

int solution(char* s) {
    int n = strlen(s);
    minCost = INT_MAX;
    backtrack(s, 0, n);
    return minCost;
}

int main() {
    char s[1001];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    int result = solution(s);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(2^n)

Each position can be part of 0 or more operations, leading to exponential possibilities

⚠ Quadratic Growth

Space Complexity

O(n)

Space for storing current string state and recursion stack

⚡ Linearithmic Space

12.8K Views

Medium Frequency

~15 min Avg. Time

456 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Try All Possible Operations — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler