Scale Engineer

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 <= 105
  • 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.

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

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.

Solutions

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 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 →

Next problem