Minimum Number of Changes to Make Binary String Beautiful

MEDIUM

Description

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

Checkout 2 different approaches to solve Minimum Number of Changes to Make Binary String Beautiful. Click on different approaches to view the approach and algorithm in detail.

Dynamic Programming Approach

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.

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.

class Solution {
    public int minChanges(String s) {
        int n = s.length();
        int[] dp = new int[n + 1];
        java.util.Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;

        for (int i = 2; i <= n; i += 2) {
            for (int j = 0; j < i; j += 2) {
                // Substring from index j to i-1
                String sub = s.substring(j, i);
                int ones = 0;
                for (char c : sub.toCharArray()) {
                    if (c == '1') {
                        ones++;
                    }
                }
                int zeros = sub.length() - ones;
                int cost = Math.min(zeros, ones);
                
                if (dp[j] != Integer.MAX_VALUE) {
                    dp[i] = Math.min(dp[i], dp[j] + cost);
                }
            }
        }
        return dp[n];
    }
}

Complexity Analysis

Time Complexity: 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 Complexity: O(n) to store the DP array `dp` of size `n+1`.

Pros and Cons

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.

Code Solutions

Checking out 3 solutions in different languages for Minimum Number of Changes to Make Binary String Beautiful. Click on different languages to view the code.

class Solution {
public
  int minChanges(String s) {
    int ans = 0;
    for (int i = 1; i < s.length(); i += 2) {
      if (s.charAt(i) != s.charAt(i - 1)) {
        ++ans;
      }
    }
    return ans;
  }
}

Video Solution

Watch the video walkthrough for Minimum Number of Changes to Make Binary String Beautiful

Data Structures:

String