# Minimum Number of Changes to Make Binary String Beautiful
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimum-number-of-changes-to-make-binary-string-beautiful)
Canonical: https://scaleengineer.com/dsa/problems/minimum-number-of-changes-to-make-binary-string-beautiful
**Data structures:** String
---
## 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 <= 105`
* `s` has an even length.
* `s[i]` is either `'0'` or `'1'`.

# Approaches
## 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.
**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`.
**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.
### Explanation
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.

```java
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];
    }
}
```
### 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.

## Greedy Iteration Over Pairs
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.
**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.
**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).
### Explanation
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.

```java
class Solution {
    public int minChanges(String s) {
        int changes = 0;
        // Iterate through the string in steps of 2
        for (int i = 0; i < s.length(); i += 2) {
            // Check if the characters in the pair are different
            if (s.charAt(i) != s.charAt(i + 1)) {
                changes++;
            }
        }
        return changes;
    }
}
```
### 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`.

# Solutions
### Java

```java
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;
  }
}

```

### Python

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

```

### CPP

```cpp
class Solution {
public:
  int minChanges(string s) {
    int ans = 0;
    int n = s.size();
    for (int i = 1; i < n; i += 2) {
      ans += s[i] != s[i - 1];
    }
    return ans;
  }
};

```