2914 Minimum Changes to Make Binary String Beautiful

Q: Is Minimum Number of Changes to Make Binary String Beautiful easy or hard?

The problem is categorized as Medium on LeetCode, but the core logic is relatively straightforward once the pair constraint is recognized. Candidates who quickly identify that each pair can be evaluated independently usually solve it in a few lines of code.

Q: Minimum Number of Changes to Make Binary String Beautiful Python/Java solution

In Python or Java, the solution typically loops through the string with a step of two and compares s[i] with s[i+1]. Each mismatch increases the change count by one. This implementation runs in O(n) time and uses constant extra space.

Q: How to solve Minimum Number of Changes to Make Binary String Beautiful in O(n)?

Traverse the string from left to right in steps of two. For each pair (i, i+1), check whether both characters are equal. If they differ, increment the change counter because one modification is needed to make the pair identical. Continue until the end of the string.

Q: What is the best approach for Minimum Number of Changes to Make Binary String Beautiful?

The optimal approach is to iterate through the string in pairs and compare adjacent characters. If a pair like '01' or '10' appears, one change is required to make both characters equal. This greedy observation works because each pair is independent. The algorithm runs in O(n) time and O(1) space.

Q: Is Minimum Number of Changes to Make Binary String Beautiful asked at Google/Amazon/Meta?

String manipulation and greedy pair-check problems similar to this appear frequently in interviews at companies like Amazon, Google, and Meta. While this exact problem may vary, the underlying pattern of analyzing fixed-size groups in a string is common in technical interviews.

Q: What data structure is used in Minimum Number of Changes to Make Binary String Beautiful?

The problem mainly relies on basic string traversal. No complex data structures are required—only simple iteration and character comparison. A counter variable tracks how many pairs require modification.

Q: What is the time complexity of Minimum Number of Changes to Make Binary String Beautiful?

The time complexity is O(n), where n is the length of the binary string. The algorithm scans the string once and evaluates characters in pairs. Space complexity remains O(1) since only a counter variable is needed.

The problem

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.

Example 1:

Input: s = "1001"
Output: 2
Explanation: We change s[1] to 1 and s[3] to 0 to get string "1100".
It can be seen that the string "1100" is beautiful because we can partition it into "11|00".
It can be proven that 2 is the minimum number of changes needed to make the string beautiful.

Example 2:

Input: s = "10"
Output: 1
Explanation: We change s[1] to 1 to get string "11".
It can be seen that the string "11" is beautiful because we can partition it into "11".
It can be proven that 1 is the minimum number of changes needed to make the string beautiful.

Example 3:

Input: s = "0000"
Output: 0
Explanation: We don't need to make any changes as the string "0000" is beautiful already.

Constraints:

2 <= s.length <= 10⁵
s has an even length.
s[i] is either '0' or '1'.

Approach overview

Problem Overview: You are given a binary string s of even length. A string is considered beautiful if every consecutive pair of characters (s[0], s[1], s[2], s[3], …) contains identical values. The task is to compute the minimum number of character changes required to satisfy this rule.

Approach 1: Check Pairs of Adjacent Characters (O(n) time, O(1) space)

The simplest observation: each pair of positions must contain the same bit. Iterate through the string in steps of two and compare s[i] with s[i+1]. If the two characters differ (01 or 10), one change is required to make them equal. Either character can be flipped, so the minimum cost per mismatched pair is exactly one operation. This approach works because each pair is independent of the others—changing one pair never affects another pair. The algorithm performs a single linear scan and counts mismatches, making it optimal with O(n) time and constant O(1) space.

Approach 2: Using Sliding Window for Efficient Changes (O(n) time, O(1) space)

This approach frames the same idea using a window of size two. Maintain a sliding window over the string and process characters in pairs. For every window [i, i+1], check whether both characters match. If they differ, increment the change counter because one modification is required to make the pair uniform. After evaluating the window, move it forward by two positions to process the next pair. The sliding window interpretation is useful when you are used to solving sliding window problems or when adapting the logic to variations where window size might change. Despite the different framing, the algorithm still performs a single pass over the string.

The key insight is that the beautiful condition operates strictly on fixed-size pairs. No global restructuring or dynamic programming is required. Each pair contributes either 0 changes (if both bits match) or 1 change (if they differ). Because of this independence, a greedy local check produces the optimal result.

This problem mainly tests comfort with basic iteration and pattern recognition in string processing. Many candidates initially overthink it with frequency counts or substring replacements, but the structure of the constraint immediately reduces it to pair comparisons.

Recommended for interviews: Approach 1 is what interviewers typically expect. It shows you recognized the pair independence and implemented the greedy check in a single pass. The sliding window framing is conceptually equivalent but can help demonstrate familiarity with common algorithmic patterns.

Approach 1: Approach 1: Check Pairs of Adjacent Characters

To make the binary string beautiful, we need to ensure that each pair of adjacent characters forms a part of a longer sequence of identical numbers. For instance, if there is '10' or '01', we can choose to change one of the characters to make the pair '11' or '00'. We will count how many changes are needed to make all pairs in the desired format.

Since the string length is even, we can consider every odd index with its preceding even index in the string. We will check how many such pairs would need to be changed either to '00' or '11'. The sum of these changes will be our answer.

Python

def min_changes_to_beautiful(s):
    changes = 0
    for i in range(0, len(s), 2):
        if s[i] != s[i + 1]:
            changes += 1
    return changes

s = "1001"
print(min_changes_to_beautiful(s))

Java

public class BinaryString {
    public static int minChangesToBeautiful(String s) {
        int changes = 0;
        for (int i = 0; i < s.length(); i += 2) {
            if (s.charAt(i) != s.charAt(i + 1)) {
                changes++;
            }
        }
        return changes;
    }

    public static void main(String[] args) {
        String s = "1001";
        System.out.println(minChangesToBeautiful(s));
    }
}

C++

#include <iostream>
#include <string>
using namespace std;

int minChangesToBeautiful(string s) {
    int changes = 0;
    for (size_t i = 0; i < s.length(); i += 2) {
        if (s[i] != s[i + 1]) {
            changes++;
        }
    }
    return changes;
}

int main() {
    string s = "1001";
    cout << minChangesToBeautiful(s) << endl;
    return 0;
}

JavaScript

function minChangesToBeautiful(s) {
    let changes = 0;
    for (let i = 0; i < s.length; i += 2) {
        if (s[i] !== s[i + 1]) {
            changes++;
        }
    }
    return changes;
}

const s = "1001";
console.log(minChangesToBeautiful(s));

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

int minChangesToBeautiful(char *s) {
    int length = strlen(s);
    int changes = 0;
    for (int i = 0; i < length; i += 2) {
        if (s[i] != s[i+1]) {
            changes++;
        }
    }
    return changes;
}

int main() {
    char s[] = "1001";
    int result = minChangesToBeautiful(s);
    printf("%d\n", result);
    return 0;
}

using System;

class Program {
    static int MinChangesToBeautiful(string s) {
        int changes = 0;
        for (int i = 0; i < s.Length; i += 2) {
            if (s[i] != s[i + 1]) {
                changes++;
            }
        }
        return changes;
    }

    static void Main() {
        string s = "1001";
        Console.WriteLine(MinChangesToBeautiful(s));
    }
}

The function min_changes_to_beautiful iterates over pairs and counts how many such pairs have different characters. For each mismatch, it increments a total changes counter and then returns it.

Complexity

Time Complexity: O(n), where n is the length of the input string. One linear pass.
Space Complexity: O(1), using minimal auxiliary space.

Try this approach in the editor

Approach 2: Approach 2: Using Sliding Window for Efficient Changes

This approach utilizes a sliding window that calculates the cumulative changes required to transform each segment of the string into either '00' or '11'. While iterating over pairs of characters, we check the discrepancy from '00' alternations and '11' alternations. To achieve this, two patterns are monitored: one representing making all pairs '00' and the other '11'. The minimum between these two paths will give the total minimum steps needed.

Python

def min_changes_to_beautiful(s):
    changes_pattern1 = 0
    changes_pattern2 = 0
    for i in range(len(s)):
        if i % 2 == 0:
            if s[i] != '0':
                changes_pattern1 += 1
            if s[i] != '1':
                changes_pattern2 += 1
        else:
            if s[i] != '1':
                changes_pattern1 += 1
            if s[i] != '0':
                changes_pattern2 += 1
    return min(changes_pattern1, changes_pattern2)

s = "1001"
print(min_changes_to_beautiful(s))

Java

public class BinaryString {
    public static int minChangesToBeautiful(String s) {
        int changesPattern1 = 0, changesPattern2 = 0;
        for (int i = 0; i < s.length(); i++) {
            if (i % 2 == 0) {
                if (s.charAt(i) != '0') changesPattern1++;
                if (s.charAt(i) != '1') changesPattern2++;
            } else {
                if (s.charAt(i) != '1') changesPattern1++;
                if (s.charAt(i) != '0') changesPattern2++;
            }
        }
        return Math.min(changesPattern1, changesPattern2);
    }

    public static void main(String[] args) {
        String s = "1001";
        System.out.println(minChangesToBeautiful(s));
    }
}

C++

#include <iostream>
#include <string>
using namespace std;

int minChangesToBeautiful(string s) {
    int changesPattern1 = 0, changesPattern2 = 0;
    for (size_t i = 0; i < s.length(); i++) {
        if (i % 2 == 0) {
            if (s[i] != '0') changesPattern1++;
            if (s[i] != '1') changesPattern2++;
        } else {
            if (s[i] != '1') changesPattern1++;
            if (s[i] != '0') changesPattern2++;
        }
    }
    return min(changesPattern1, changesPattern2);
}

int main() {
    string s = "1001";
    cout << minChangesToBeautiful(s) << endl;
    return 0;
}

JavaScript

function minChangesToBeautiful(s) {
    let changesPattern1 = 0, changesPattern2 = 0;
    for (let i = 0; i < s.length; i++) {
        if (i % 2 === 0) {
            if (s[i] !== '0') changesPattern1++;
            if (s[i] !== '1') changesPattern2++;
        } else {
            if (s[i] !== '1') changesPattern1++;
            if (s[i] !== '0') changesPattern2++;
        }
    }
    return Math.min(changesPattern1, changesPattern2);
}

const s = "1001";
console.log(minChangesToBeautiful(s));

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

int minChangesToBeautiful(char *s) {
    int changesPattern1 = 0, changesPattern2 = 0;
    for (int i = 0; i < strlen(s); i++) {
        if (i % 2 == 0) {
            if (s[i] != '0') changesPattern1++;
            if (s[i] != '1') changesPattern2++;
        } else {
            if (s[i] != '1') changesPattern1++;
            if (s[i] != '0') changesPattern2++;
        }
    }
    return changesPattern1 < changesPattern2 ? changesPattern1 : changesPattern2;
}

int main() {
    char s[] = "1001";
    int result = minChangesToBeautiful(s);
    printf("%d\n", result);
    return 0;
}

using System;

class Program {
    static int MinChangesToBeautiful(string s) {
        int changesPattern1 = 0, changesPattern2 = 0;
        for (int i = 0; i < s.Length; i++) {
            if (i % 2 == 0) {
                if (s[i] != '0') changesPattern1++;
                if (s[i] != '1') changesPattern2++;
            } else {
                if (s[i] != '1') changesPattern1++;
                if (s[i] != '0') changesPattern2++;
            }
        }
        return Math.Min(changesPattern1, changesPattern2);
    }

    static void Main() {
        string s = "1001";
        Console.WriteLine(MinChangesToBeautiful(s));
    }
}

Python's method assesses two possible sequences changing the binary string into either complete '0101...' or '1010...' alignments, outputting how many steps are necessary to adhere to the correct pattern altogether.

Complexity

Time Complexity: O(n), considering n is a linear scan of the input string.
Space Complexity: O(1), only a few scalar variables are used.

Try this approach in the editor

Approach 3: Counting

We only need to traverse all odd indices 1, 3, 5, cdots of the string s. If the current odd index is different from the previous index, i.e., s[i] \ne s[i - 1], we need to modify the current character so that s[i] = s[i - 1]. Therefore, the answer needs to be incremented by 1.

After the traversal, we return the answer.

The time complexity is O(n), where n is the length of the string s. The space complexity is O(1).

TypeScript

function minChanges(s: string): number {
    let ans = 0;
    for (let i = 1; i < s.length; i += 2) {
        if (s[i] !== s[i - 1]) {
            ++ans;
        }
    }
    return ans;
}

func minChanges(s string) (ans int) {
	for i := 1; i < len(s); i += 2 {
		if s[i] != s[i-1] {
			ans++
		}
	}
	return
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Approach 1: Check Pairs of Adjacent Characters	Time Complexity: O(n), where n is the length of the input string. One linear pass. Space Complexity: O(1), using minimal auxiliary space.
Approach 2: Using Sliding Window for Efficient Changes	Time Complexity: O(n), considering n is a linear scan of the input string. Space Complexity: O(1), only a few scalar variables are used.
Counting	–

Complexity analysis

Approach	Time	Space	When to Use
Check Pairs of Adjacent Characters	O(n)	O(1)	Best general solution. Simple linear scan with constant memory.
Sliding Window (size 2)	O(n)	O(1)	Useful when applying a consistent sliding-window pattern or adapting to similar problems.

Frequently asked questions

Is Minimum Number of Changes to Make Binary String Beautiful easy or hard?

The problem is categorized as Medium on LeetCode, but the core logic is relatively straightforward once the pair constraint is recognized. Candidates who quickly identify that each pair can be evaluated independently usually solve it in a few lines of code.

Minimum Number of Changes to Make Binary String Beautiful Python/Java solution

In Python or Java, the solution typically loops through the string with a step of two and compares s[i] with s[i+1]. Each mismatch increases the change count by one. This implementation runs in O(n) time and uses constant extra space.

How to solve Minimum Number of Changes to Make Binary String Beautiful in O(n)?

Traverse the string from left to right in steps of two. For each pair (i, i+1), check whether both characters are equal. If they differ, increment the change counter because one modification is needed to make the pair identical. Continue until the end of the string.

What is the best approach for Minimum Number of Changes to Make Binary String Beautiful?

The optimal approach is to iterate through the string in pairs and compare adjacent characters. If a pair like '01' or '10' appears, one change is required to make both characters equal. This greedy observation works because each pair is independent. The algorithm runs in O(n) time and O(1) space.

Is Minimum Number of Changes to Make Binary String Beautiful asked at Google/Amazon/Meta?

String manipulation and greedy pair-check problems similar to this appear frequently in interviews at companies like Amazon, Google, and Meta. While this exact problem may vary, the underlying pattern of analyzing fixed-size groups in a string is common in technical interviews.

What data structure is used in Minimum Number of Changes to Make Binary String Beautiful?

The problem mainly relies on basic string traversal. No complex data structures are required—only simple iteration and character comparison. A counter variable tracks how many pairs require modification.

What is the time complexity of Minimum Number of Changes to Make Binary String Beautiful?

The time complexity is O(n), where n is the length of the binary string. The algorithm scans the string once and evaluates characters in pairs. Space complexity remains O(1) since only a counter variable is needed.

Minimum Number of Changes to Make Binary String Beautiful solution and explanation

The problem

Approach overview

Approach 1: Approach 1: Check Pairs of Adjacent Characters

Approach 2: Approach 2: Using Sliding Window for Efficient Changes

Approach 3: Counting

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Minimum Number of Changes to Make Binary String Beautiful solution and explanation

The problem

Approach overview

Approach 1: Approach 1: Check Pairs of Adjacent Characters

Approach 2: Approach 2: Using Sliding Window for Efficient Changes

Approach 3: Counting

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems