• Posts

Problem 2914 Minimum Number of Changes to Make Binary String Beautiful

Problem Statement

Link - Problem 2914

Question

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

Solution

class Solution {
public:
    int minChanges(string s) {
        int changes = 0;
        int size = s.size();
        for(int i=0;i<size; i= i+2){
            if(s[i]!=s[i+1])
                changes++;
        }
        return changes;

    }
};

Complexity Analysis

| Algorithm                 | Time Complexity | Space Complexity |
| ------------------------- | --------------- | ---------------- |
| Modified linear traversal | O(n)            | O(1)             |

Explanation

Intial Thoughts

To approach this problem, we should first identify the constraints given: the string has an even length and each character is either ‘0’ or ‘1’. Then, consider what makes a string ‘beautiful’: it can be divided into substrings of even lengths where each substring contains only ‘0’s or only ‘1’s. We need to think about how to efficiently compare and possibly change characters in pairs to achieve this. Key points to consider are: the impact of changing a character, how to minimize changes, and ensuring the resulting string can be divided as specified.

Intuitive Analysis

Intuitively, solving this problem involves iteratively checking each pair of adjacent characters in the string. If a pair has different characters, we must change one to match the other to meet the ‘beautiful’ criteria. The provided solution code reflects this intuition by looping through the string two characters at a time and incrementing a ‘changes’ counter whenever a mismatch is found. Notably, this approach works because it ensures that each substring of length 2 can be considered ‘beautiful’ by itself, thereby making the entire string ‘beautiful’ when all such substrings are considered together. Key aspects of this analysis include recognizing the importance of pairs, understanding how changes affect the string’s beauty, and optimizing the process to minimize the number of changes needed.

1. Intuition

• The problem requires finding the minimum number of changes to make a binary string beautiful, which means it can be partitioned into substrings of even length containing only 1’s or 0’s.
• To approach this problem, we need to think about how to partition the string into substrings of even length.
• We can observe that if a substring has an even length, it can be made beautiful by changing all its characters to either 0 or 1.
• The key insight is that we only need to consider pairs of adjacent characters in the string.
• If a pair of adjacent characters is different, we need to change one of them to make the substring beautiful.
• By iterating over the string in steps of 2, we can count the number of pairs that need to be changed.
• This approach works because it ensures that each substring of even length contains only 1’s or 0’s.

2. Implementation

• We start by initializing a variable changes to 0, which will store the minimum number of changes required.
• We then iterate over the string s in steps of 2 using a for loop: for(int i=0;i<size; i= i+2).
• Inside the loop, we check if the current pair of characters is different: if(s[i]!=s[i+1]).
• If the pair is different, we increment the changes variable by 1: changes++.
• Finally, we return the total number of changes required: return changes.
• The time complexity of this solution is O(n), where n is the length of the string, because we only iterate over the string once.
• The space complexity is O(1), because we only use a constant amount of space to store the changes variable.

Complexity Analysis

Time Complexity:

• The algorithm iterates over the string s using a for loop that increments i by 2 in each iteration, resulting in a linear traversal of the string.
• The dominant operation in the code is the comparison s[i]!=s[i+1], which is performed inside the loop and has a constant time complexity of O(1).
• Given that the loop runs size/2 times, where size is the length of the string s, the overall time complexity is O(n), where n is the length of the string s, since we drop constant factors in Big O notation.

Space Complexity:

• The algorithm only uses a constant amount of space to store the variables changes and size, regardless of the input size.
• The input string s is not modified, and no additional data structures are used that scale with the input size.
• Therefore, the space complexity is O(1), indicating that the memory usage does not grow with the size of the input.

Footnote

This question is rated as Medium difficulty.

Hints

For any valid partition, since each part consists of an even number of the same characters, we can further partition each part into lengths of exactly 2.

After noticing the first hint, we can decompose the whole string into disjoint blocks of size 2 and find the minimum number of changes required to make those blocks beautiful.