LeetCode 2914 - Minimum Number of Changes to Make Binary String Beautiful

You are given a binary string s whose length is guaranteed to be even. A binary string contains only the characters '0' and '1'. A string is considered beautiful if it can be divided into one or more contiguous substrings such that: - Every substring has even length.

leetcodemediumstring

LeetCode Problem 2914

Difficulty: 🟡 Medium
Topics: String

Solution

Problem Understanding

You are given a binary string s whose length is guaranteed to be even. A binary string contains only the characters '0' and '1'.

A string is considered beautiful if it can be divided into one or more contiguous substrings such that:

  • Every substring has even length.
  • Every substring consists entirely of the same character.

For example:

  • "1100" is beautiful because it can be partitioned as "11 | 00".
  • "0000" is beautiful because the whole string itself is an even-length block of identical characters.
  • "1010" is not beautiful because any partition into even-length pieces will contain mixed characters.

You are allowed to change any character from '0' to '1' or from '1' to '0'. The goal is to compute the minimum number of character changes needed to transform the string into a beautiful string.

The constraints are important:

  • 2 <= s.length <= 10^5
  • The length is always even.

The input size tells us that an efficient linear time solution is expected. Any algorithm that tries many combinations or performs expensive dynamic programming over all partitions would be unnecessary and potentially too slow.

The key observation hidden in the problem is that every valid substring must have even length and contain only one character. This means characters naturally need to form pairs of equal values. Since the entire string length is even, we can process the string two characters at a time.

Some important edge cases include:

  • A string already beautiful, such as "0000", where the answer should be 0.
  • A string where every adjacent pair differs, such as "1010", where every pair requires one modification.
  • The smallest possible input length, "01" or "10".
  • Long alternating patterns where many changes are needed.

The problem guarantees the string length is even, so we never need to worry about incomplete pairs.

Approaches

Brute Force Approach

A brute force solution would attempt to explore all possible ways to modify characters and then check whether the resulting string is beautiful.

One way to think about this is:

  • For every character, choose whether to keep it or flip it.
  • Generate all possible transformed binary strings.
  • For each transformed string, verify whether it can be partitioned into valid even-length uniform substrings.
  • Return the minimum number of flips among all valid candidates.

This approach is correct because it exhaustively checks every possible transformed string. However, it is completely impractical.

If the string has length n, there are 2^n possible transformed strings. Even for n = 50, this becomes astronomically large, while the actual constraint allows n up to 100000.

Therefore, brute force is far too slow.

Optimal Approach

The key insight is that every valid substring must have even length and contain identical characters only.

This means every adjacent pair of characters can independently form a valid block:

  • "00" is valid.
  • "11" is valid.
  • "01" is invalid and requires one change.
  • "10" is invalid and requires one change.

A longer valid substring like "0000" can also be viewed as two valid adjacent pairs:

  • "00 | 00"

Therefore, the minimum number of changes is simply the number of adjacent pairs where the two characters differ.

We process the string in steps of two:

  • If s[i] == s[i + 1], no change is needed.
  • Otherwise, exactly one change is needed to make the pair uniform.

This gives a simple linear time solution.

Approach Time Complexity Space Complexity Notes
Brute Force O(2^n * n) O(n) Tries every possible transformed string
Optimal O(n) O(1) Count mismatched adjacent pairs

Algorithm Walkthrough

  1. Initialize a variable changes to 0.

This variable will store the minimum number of modifications required. 2. Traverse the string two characters at a time.

Since the string length is guaranteed to be even, we can safely process indices:

  • (0, 1)
  • (2, 3)
  • (4, 5)
  • and so on.
  1. For each pair, compare the two characters.

If the characters are already equal, the pair is valid and requires no changes.

Examples:

  • "00" is already beautiful.
  • "11" is already beautiful.
  1. If the characters differ, increment changes by 1.

Examples:

  • "01" requires changing either character.
  • "10" also requires one modification.

Only one change is ever necessary because changing either character makes the pair uniform. 5. Continue until all pairs are processed. 6. Return changes.

Why it works

A beautiful string can always be partitioned into even-length uniform blocks. Any such block can be decomposed into adjacent equal pairs. Therefore, ensuring every adjacent pair contains identical characters is sufficient to guarantee the whole string is beautiful.

Each mismatched pair independently requires exactly one modification, and no pair affects another pair. Because of this independence, summing the number of mismatched pairs gives the global minimum number of changes.

Python Solution

class Solution:
    def minChanges(self, s: str) -> int:
        changes = 0

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

        return changes

The implementation directly follows the optimal algorithm.

The variable changes stores the running answer.

The loop increments by 2, ensuring we process the string pair by pair. Because the input length is guaranteed to be even, accessing s[i + 1] is always safe.

Inside the loop, we compare the two characters in the current pair:

  • If they are equal, the pair already satisfies the requirement.
  • If they differ, we increment the answer because one modification is necessary.

Finally, the function returns the accumulated count.

Go Solution

func minChanges(s string) int {
    changes := 0

    for i := 0; i < len(s); i += 2 {
        if s[i] != s[i+1] {
            changes++
        }
    }

    return changes
}

The Go implementation mirrors the Python logic almost exactly.

Strings in Go can be indexed directly using s[i], which returns a byte. Since the input contains only ASCII characters '0' and '1', byte comparison is perfectly safe and efficient.

No additional memory allocation is required, so the solution maintains constant extra space usage.

Worked Examples

Example 1

Input:

s = "1001"

We process the string in pairs.

Pair Index Pair Equal? Changes
(0,1) "10" No 1
(2,3) "01" No 2

Final answer:

2

One possible transformed string is:

"1100"

Partition:

"11 | 00"

Example 2

Input:

s = "10"
Pair Index Pair Equal? Changes
(0,1) "10" No 1

Final answer:

1

We can change the string to:

"11"

Example 3

Input:

s = "0000"
Pair Index Pair Equal? Changes
(0,1) "00" Yes 0
(2,3) "00" Yes 0

Final answer:

0

The string is already beautiful.

Complexity Analysis

Measure Complexity Explanation
Time O(n) We scan the string once
Space O(1) Only a few variables are used

The algorithm performs a single pass through the string, examining each character exactly once as part of a pair comparison.

No auxiliary data structures proportional to the input size are created, so the extra memory usage remains constant.

Test Cases

class Solution:
    def minChanges(self, s: str) -> int:
        changes = 0

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

        return changes

sol = Solution()

assert sol.minChanges("1001") == 2  # Example with two mismatched pairs
assert sol.minChanges("10") == 1  # Smallest input requiring one change
assert sol.minChanges("0000") == 0  # Already beautiful
assert sol.minChanges("11") == 0  # Single valid pair
assert sol.minChanges("01") == 1  # Single invalid pair
assert sol.minChanges("1010") == 2  # Every pair mismatches
assert sol.minChanges("0011") == 0  # Two valid pairs
assert sol.minChanges("11001100") == 0  # Larger already beautiful string
assert sol.minChanges("11110000") == 0  # Long valid uniform blocks
assert sol.minChanges("01010101") == 4  # Maximum changes for length 8
assert sol.minChanges("00110011") == 0  # Multiple valid pair groups
assert sol.minChanges("0110") == 2  # Both pairs invalid
Test Why
"1001" Verifies multiple mismatched pairs
"10" Smallest nontrivial case
"0000" Already beautiful
"11" Single valid pair
"01" Single invalid pair
"1010" Every pair requires modification
"0011" Multiple correct pairs
"11001100" Larger valid input
"11110000" Long uniform regions
"01010101" Worst case alternating pattern
"00110011" Repeated valid structure
"0110" Multiple invalid pairs

Edge Cases

Smallest Possible Input

The minimum allowed string length is 2. Inputs such as "01" or "10" are important because there is only one pair to evaluate. Some implementations accidentally assume longer strings or mishandle loop boundaries.

This implementation safely handles length 2 because the loop processes exactly one pair and terminates correctly.

Already Beautiful Strings

Inputs like "0000" or "11110000" already satisfy the requirements. A buggy implementation might accidentally overcount changes or try unnecessary modifications.

This solution only increments the counter when adjacent characters differ, so already valid pairs contribute zero changes.

Fully Alternating Strings

Strings such as "10101010" represent the worst-case scenario where every pair mismatches.

Each pair independently requires one modification, so the answer equals half the string length.

The implementation handles this naturally because every pair comparison fails and increments the counter exactly once.