Minimum Number of Changes to Make a Binary String Beautiful | Leetcode : 2914

In this LeetCode problem, we're tasked with transforming a given binary string into a "beautiful" string. A beautiful string is one that can be partitioned into substrings, each containing only 0s or 1s and having an even length.

To achieve this beauty, we're allowed to change any character in the string to either 0 or 1. The challenge lies in determining the minimum number of such changes required.

Intuition and Approach

To solve this problem efficiently, we can employ a greedy approach. We'll iterate through the string, keeping track of the current character and the count of consecutive occurrences of that character.

1. Iterate and Count:

   • Start with the first character and initialize a count to 1.
   • As we traverse the string, we increment the count if the current character matches the previous one.
   • If the current character is different, we've encountered a new substring.

2. Handle Odd-Length Substrings:

   • If the current count is odd, we'll need to make a change.
     • If it's the last character, we can simply change it.
     • Otherwise, we can either change the current character or the next character to match the previous substring. We choose the option that requires fewer changes.

3. Update the Current Character and Count:

   • After handling odd-length substrings, we update the current character and reset the count to 1 for the new substring.

Code Implementation

Here's the C++ code implementing this approach:

class Solution {

public:

    int minChanges(string s) {

        int n = s.length();

        int changes = 0, count = 1;

        char ch = s[0];

        for (int i = 1; i < n; ++i) {

            if (s[i] == ch) {

                count++;

            } else {

                if (count % 2 == 1) {

                    changes++;

                    if (i + 1 < n && s[i + 1] == ch) {

                        count = 1; // Start a new substring with the next character

                    }

                }

                ch = s[i];

                count = 1;

            }

        }

        return changes;

    }

};

Explanation of the Code:

1. Initialization:

   • changes: Stores the total number of changes required.
   • count: Keeps track of the current character's consecutive occurrences.
   • ch: Stores the current character.

2. Iteration:

   • We iterate through the string, starting from the second character.
   • If the current character matches the previous one, we increment the count.
   • If they don't match:
     • If the current count is odd, we need to make a change. We choose the more efficient option between changing the current character or the next character.
     • We update the ch and reset the count for the new substring.

3. Return the Result:

   • After the loop, changes will hold the minimum number of changes required to make the string beautiful.

Time and Space Complexity:

• Time complexity: O(N), where N is the length of the string.
• Space complexity: O(1), as we use constant extra space.

By following this approach, we can efficiently determine the minimum number of changes needed to transform a given binary string into a beautiful one.