{x}
blog image

Minimum Changes To Make Alternating Binary String

You are given a string s consisting only of the characters '0' and '1'. In one operation, you can change any '0' to '1' or vice versa.

The string is called alternating if no two adjacent characters are equal. For example, the string "010" is alternating, while the string "0100" is not.

Return the minimum number of operations needed to make s alternating.

 

Example 1:

Input: s = "0100"
Output: 1
Explanation: If you change the last character to '1', s will be "0101", which is alternating.

Example 2:

Input: s = "10"
Output: 0
Explanation: s is already alternating.

Example 3:

Input: s = "1111"
Output: 2
Explanation: You need two operations to reach "0101" or "1010".

 

Constraints:

  • 1 <= s.length <= 104
  • s[i] is either '0' or '1'.

Solution Explanation

The problem asks for the minimum number of operations to make a binary string alternating. An alternating string is defined as a string where no two adjacent characters are equal (e.g., "0101" or "1010"). The solution efficiently determines this minimum by considering two possible alternating patterns and choosing the one requiring fewer changes.

Approach

  1. Two Possible Alternating Patterns: There are only two possible alternating patterns for a binary string: "010101..." and "101010...".

  2. Counting Changes for Each Pattern: For each pattern, the algorithm counts the number of characters in the input string that need to be changed to match that pattern.

  3. Minimum of Changes: The minimum number of operations is simply the smaller of the change counts from the two patterns.

Time and Space Complexity

  • Time Complexity: O(n), where n is the length of the input string. The algorithm iterates through the string once for each pattern.

  • Space Complexity: O(1). The algorithm uses a constant amount of extra space, regardless of the input string's size.

Code Explanation (Python as an Example)

The Python code efficiently implements this approach:

class Solution:
    def minOperations(self, s: str) -> int:
        cnt = sum(c != '01'[i & 1] for i, c in enumerate(s))
        return min(cnt, len(s) - cnt)

  1. cnt = sum(c != '01'[i & 1] for i, c in enumerate(s)): This line is the core of the algorithm. Let's break it down:

    • enumerate(s): This iterates through the string s along with its indices.
    • '01'[i & 1]: This cleverly generates the expected character for the "0101..." pattern. i & 1 is a bitwise AND operation. It's 0 for even indices (where we expect '0') and 1 for odd indices (where we expect '1'). This efficiently selects '0' or '1' based on the index.
    • c != '01'[i & 1]: This compares the actual character c at index i with the expected character from the "0101..." pattern. It evaluates to True (1) if they are different (a change is needed), and False (0) otherwise.
    • sum(...): This sums up all the True values (i.e., the number of characters that need changing for the "0101..." pattern).

  2. return min(cnt, len(s) - cnt): This returns the minimum between the number of changes needed for the "0101..." pattern (cnt) and the number of changes needed for the "1010..." pattern (len(s) - cnt). The number of changes for the "1010..." pattern is simply the total length minus the number of changes for "0101...". This is because if you need x changes for one pattern, you need n-x changes for the other pattern, where n is the length of the string.

The code in other languages follows a similar logic, adapting the syntax to the specific language features. The core idea remains consistent: count the changes for one pattern and infer the other pattern's changes by subtracting from the total length.