Problem of The Day: Minimum Number of Changes to Make Binary String Beautiful

Problem Statement

Intuition

The problem involves finding the minimum number of changes required to make certain conditions meet within a string. My first intuition was to iterate through the string in pairs to detect mismatches between adjacent characters. For each mismatch, I would increment a counter to track the number of changes required.

Approach

To solve this problem:

1. Start by calculating the length of the string.
2. Initialize a result variable (res) to count the number of required changes.
3. Loop through the string with a step of 2 to handle pairs of characters at positions i and i+1.
4. For each pair, if the characters at i and i+1 are different, increment the counter res by one, since we need to change one of them to make the pair identical.
5. Finally, return res as the total number of changes required.

This approach allows us to efficiently count the required changes in a single pass through the string.

Complexity

• Time complexity: \(O(n)\), where (n) is the length of the string. This is because we are iterating through the string once, checking pairs in constant time.
• Space complexity: \(O(1)\), as we are only using a fixed amount of extra space for the counter.

Code

class Solution:
    def minChanges(self, s: str) -> int:
        N = len(s)
        res = 0
        for i in range(0, N - 1, 2):  # Ensuring we don't go out of bounds
            if s[i] != s[i + 1]:
                res += 1
        return res

Editorial

Approach 1: Greedy

class Solution:
    def minChanges(self, s: str) -> int:
        # Initialize with first character
        current_char = s[0]

        consecutive_count = 0
        min_changes_required = 0

        # Iterate through each character
        for char in s:
            # If current character matches the previous sequence
            if char == current_char:
                consecutive_count += 1
                continue

            # If we have even count of characters, start new sequence
            if consecutive_count % 2 == 0:
                consecutive_count = 1
            # If odd count, we need to change current character
            else:
                consecutive_count = 0
                min_changes_required += 1

            # Update current character for next iteration
            current_char = char

        return min_changes_required

Approach 2: Greedy (Optimized)

class Solution:
    def minChanges(self, s: str) -> int:
        min_changes_required = 0

        # Check pairs of characters (i, i+1) with step size 2
        for i in range(0, len(s), 2):
            # If characters in current pair don't match,
            # we need one change to make them equal
            if s[i] != s[i + 1]:
                min_changes_required += 1
        return min_changes_required


"""
pythonic one liner:

class Solution:
    def minChanges(self, s: str) -> int:
        # Count changes needed for each unmatched pair
        return sum(s[i] != s[i + 1] for i in range(0, len(s), 2))
"""