Minimum Number of Changes to Make Binary String Beautiful

Minimum Number of Changes to Make Binary String Beautiful - Problem

String Medium

You are given a 0-indexed binary string s having an even length.

A string is beautiful if it's possible to partition it into one or more substrings such that:

Each substring has an even length
Each substring contains only 1's or only 0's

You can change any character in s to 0 or 1.

Return the minimum number of changes required to make the string s beautiful.

Input & Output

Example 1 — Basic Case

$ Input: s = "1001"

› Output: 2

💡 Note: We can partition into pairs: "10" and "01". First pair needs 1 change (10→00 or 10→11), second pair needs 1 change (01→00 or 01→11). Total: 2 changes.

Example 2 — No Changes Needed

$ Input: s = "10"

› Output: 1

💡 Note: Only one pair "10" where characters differ, so we need 1 change to make it "00" or "11".

Example 3 — Already Beautiful

$ Input: s = "1100"

› Output: 0

💡 Note: We can partition as "11" and "00". Both substrings already contain identical characters, so 0 changes needed.

Constraints

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

Visualization

Tap to expand

Asked in

G Google 15 f Meta 12 M Microsoft 8

The key insight is that the optimal beautiful string uses pairs of identical characters. The greedy approach of checking each adjacent pair gives the minimum changes needed. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Partitions	O(2ⁿ × n)	O(n)	Try every possible way to partition the string into valid substrings
Greedy - Pair Adjacent Characters	O(n)	O(1)	Process characters in pairs from left to right, changing mismatched pairs

Brute Force - Try All Partitions — Algorithm Steps

Step 1: Generate all possible partitions with even-length substrings
Step 2: For each partition, calculate minimum changes for each substring
Step 3: Return the minimum total changes across all partitions

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Partitions

Try all possible even-length partitions

Calculate Changes

For each partition, find minimum changes per substring

Find Minimum

Return the partition requiring fewest total changes

Code -

solution.c — C

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

int memo[1001];
int memoized[1001];

int dp(const char* s, int index, int n) {
    if (index == n) return 0;
    if (memoized[index]) return memo[index];
    
    int minChanges = INT_MAX;
    // Try all even-length substrings starting at index
    for (int length = 2; length <= n - index; length += 2) {
        // Calculate changes needed for substring s[index:index+length]
        int zeros = 0;
        for (int i = index; i < index + length; i++) {
            if (s[i] == '0') zeros++;
        }
        int ones = length - zeros;
        int changes = (zeros < ones) ? zeros : ones;
        
        int result = changes + dp(s, index + length, n);
        if (result < minChanges) {
            minChanges = result;
        }
    }
    
    memo[index] = minChanges;
    memoized[index] = 1;
    return minChanges;
}

int solution(char* s) {
    int n = strlen(s);
    memset(memoized, 0, sizeof(memoized));
    return dp(s, 0, n);
}

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)

2^n possible partitions, each taking O(n) time to evaluate

✓ Linear Growth

Space Complexity

O(n)

Recursion stack depth for generating partitions

⚡ Linearithmic Space

8.9K Views

Medium Frequency

~15 min Avg. Time

432 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

Brute Force - Try All Partitions — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler