Minimum Number of Changes to Make Binary String Beautiful

Med

#2595Time: O(n^3). The two nested loops run in `O(n^2)`, and inside the inner loop, creating and iterating over the substring takes `O(n)` time. This can be optimized to `O(n^2)` by pre-calculating prefix sums of characters.Space: O(n) to store the DP array `dp` of size `n+1`.

Data structures

String

Prompt

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'.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach uses dynamic programming to solve the problem by building up a solution from smaller subproblems. We define dp[i] as the minimum number of changes to make the prefix of length i beautiful. The final answer is dp[n], where n is the length of the string. This method systematically explores all possible ways to partition the string into beautiful segments.

Algorithm

Initialize a DP array dp of size n+1, where n is the string length. dp[i] will store the minimum changes to make the prefix s[0...i-1] beautiful.
Set dp[0] = 0 and all other dp[i] to infinity.
Iterate i from 2 to n with a step of 2. This represents the length of the prefix we are trying to make beautiful.
Inside this loop, iterate j from 0 to i-2 with a step of 2. This j marks the end of a smaller beautiful prefix.
For each (i, j) pair, consider the substring s[j...i-1]. This is the last segment we are appending.
Calculate the cost to make this substring monochromatic. The cost is the minimum of the number of '0's and '1's in it.
Update the DP state: dp[i] = min(dp[i], dp[j] + cost).
After the loops complete, dp[n] will hold the minimum changes for the entire string.

Walkthrough

The core idea is that a beautiful string of length i is formed by appending a beautiful, monochromatic substring of even length to a previously computed beautiful prefix of length j < i. We can express this relationship using a recurrence relation.

Let dp[i] be the minimum changes to make the prefix s[0...i-1] beautiful. Since beautiful strings must have an even length, we only need to compute dp[i] for even values of i.

The recurrence relation is: dp[i] = min_{0 <= j < i, j is even} (dp[j] + cost(j, i-1))

Here, cost(j, i-1) is the minimum number of changes to make the substring s[j...i-1] monochromatic. This cost is calculated as min(count_of_zeros, count_of_ones) in that substring. The base case is dp[0] = 0, representing an empty prefix that is beautiful with zero changes.

We can implement this by iterating through all possible end positions i and all possible start positions j for the final segment of the partition.

1class Solution {2    public int minChanges(String s) {3        int n = s.length();4        int[] dp = new int[n + 1];5        java.util.Arrays.fill(dp, Integer.MAX_VALUE);6        dp[0] = 0;7 8        for (int i = 2; i <= n; i += 2) {9            for (int j = 0; j < i; j += 2) {10                // Substring from index j to i-111                String sub = s.substring(j, i);12                int ones = 0;13                for (char c : sub.toCharArray()) {14                    if (c == '1') {15                        ones++;16                    }17                }18                int zeros = sub.length() - ones;19                int cost = Math.min(zeros, ones);20                21                if (dp[j] != Integer.MAX_VALUE) {22                    dp[i] = Math.min(dp[i], dp[j] + cost);23                }24            }25        }26        return dp[n];27    }28}

Complexity

Time

O(n^3). The two nested loops run in `O(n^2)`, and inside the inner loop, creating and iterating over the substring takes `O(n)` time. This can be optimized to `O(n^2)` by pre-calculating prefix sums of characters.

Space

O(n) to store the DP array `dp` of size `n+1`.

Trade-offs

Pros

It is a standard and general method for solving partition-style problems.
Guarantees finding the optimal solution by exploring all valid partitions systematically.

Cons

Highly inefficient with a time complexity of O(n^3) (or O(n^2) with precomputation), which is too slow for the given constraints.
Unnecessarily complex for this problem, as it doesn't leverage the specific structure of the 'beautiful' string definition.
Requires O(n) extra space for the DP array, whereas a more optimal solution uses constant space.

This approach leverages a key observation about the problem's structure. A string is 'beautiful' if and only if it can be partitioned into monochromatic substrings of length 2. This simplifies the problem significantly, allowing for a greedy strategy. We only need to iterate through the string in pairs and count how many pairs have different characters.

Algorithm

Initialize a counter variable, changes, to 0.
Iterate through the input string s with an index i starting from 0, incrementing by 2 in each step. This processes the string in non-overlapping pairs.
In each iteration, compare the character at s[i] with the character at s[i+1].
If s.charAt(i) is not equal to s.charAt(i+1), it means one change is required to make this pair monochromatic. Increment the changes counter.
If the characters are the same, the pair is already beautiful, so do nothing.
After the loop completes, return the total value of changes.

Walkthrough

The definition of a beautiful string requires it to be partitionable into monochromatic substrings of even length. A crucial insight is that any such substring (e.g., "1111") can itself be broken down into smaller monochromatic substrings of length 2 (e.g., "11" and "11"). This means a string is beautiful if and only if it can be partitioned entirely into monochromatic pairs.

This simplifies the problem to making each non-overlapping pair of characters, (s[2k], s[2k+1]), identical. The changes made within one pair do not affect any other pair, so we can find the minimum changes for each pair independently and sum them up for the global minimum.

For each pair (s[i], s[i+1]):

If s[i] == s[i+1] (e.g., "00" or "11"), the pair is already monochromatic. The cost is 0.
If s[i] != s[i+1] (e.g., "01" or "10"), we need to make them identical. This requires exactly one change (e.g., "01" -> "00" or "11"). The cost is 1.

Therefore, the total minimum number of changes is simply the count of pairs with differing characters.

1class Solution {2    public int minChanges(String s) {3        int changes = 0;4        // Iterate through the string in steps of 25        for (int i = 0; i < s.length(); i += 2) {6            // Check if the characters in the pair are different7            if (s.charAt(i) != s.charAt(i + 1)) {8                changes++;9            }10        }11        return changes;12    }13}

Complexity

Time

O(n), where `n` is the length of the string. We perform a single pass through the string, examining each character exactly once.

Space

O(1), as we only use a few variables to keep track of the index and the count of changes, regardless of the input size.

Trade-offs

Pros

Extremely efficient with a linear time complexity, making it suitable for large inputs.
Requires only constant extra space.
Very simple to understand and implement once the key insight is clear.

Cons

The approach relies on a specific insight about the problem that might not be immediately obvious.
It is less general than a DP solution and might not be applicable if the problem constraints were slightly different (e.g., if odd-length substrings were allowed).

Solutions

Solution

1class Solution {2public3  int minChanges(String s) {4    int ans = 0;5    for (int i = 1; i < s.length(); i += 2) {6      if (s.charAt(i) != s.charAt(i - 1)) {7        ++ans;8      }9    }10    return ans;11  }12}

1class Solution:2    def minChanges(3        self, s: str) -> int: return sum(s[i] != s[i - 1] for i in range(1, len(s), 2))

1class Solution {2public:3  int minChanges(string s) {4    int ans = 0;5    int n = s.size();6    for (int i = 1; i < n; i += 2) {7      ans += s[i] != s[i - 1];8    }9    return ans;10  }11};

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem