algoadvance

1758. Minimum Changes To Make Alternating Binary String

You are given a binary string s. You are allowed to perform two types of operations on the string:

  1. Remove a character at any position.
  2. Insert a character ‘0’ or ‘1’ at any position.

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

An alternating binary string is a string in which no two adjacent characters are the same. For example, “010” and “101” are alternating binary strings, while “00” and “111” are not.

Example:

Input: s = "0100"
Output: 1
Explanation: We can remove the last character to get "010" which is an alternating string.

Clarifying Questions

  1. What is the guaranteed length range of the string s?
    • The problem usually states a reasonable constraint such as 1 <= s.length <= 10^4.
  2. Does the string contain only ‘0’s and ‘1’s?
    • Yes, as the string is binary.
  3. Are there any performance constraints we should be aware of?
    • The solution needs to handle strings up to the maximum length efficiently.

Strategy

To solve this problem, we need to convert the given string s into an alternating binary string with the minimum number of changes. An alternating binary string can start with either ‘0’ or ‘1’. We’ll consider both possibilities and count the number of changes needed for each.

  1. Pattern 1: Starts with ‘0’ and alternates (0, 1, 0, .. etc.)
  2. Pattern 2: Starts with ‘1’ and alternates (1, 0, 1, .. etc.)

We’ll compare s against both patterns and count the necessary changes for each scenario. The minimum of these two counts will be our answer.

Detailed Steps:

  1. Initialize two counters: one for counting changes for the first pattern and the other for the second pattern.
  2. Traverse the string s and for each character, compare it with the expected character in both patterns.
  3. Increment the respective counters for any mismatches.
  4. Return the minimum value between the two counters.

Code

def min_operations_to_alternate(s: str) -> int:
    n = len(s)
    
    # Two patterns to compare against
    pattern1, pattern2 = '0', '1'
    
    count1 = count2 = 0
    
    for i in range(n):
        # For pattern starting with '0' (010101...)
        if s[i] != pattern1:
            count1 += 1
        # For pattern starting with '1' (101010...)
        if s[i] != pattern2:
            count2 += 1
        
        # Alternate the patterns
        pattern1, pattern2 = pattern2, pattern1
    
    return min(count1, count2)

# Example usage
s = "0100"
print(min_operations_to_alternate(s))  # Output should be 1

Time Complexity

This approach ensures we efficiently determine the minimum changes needed to convert the binary string into an alternating binary string.

Try our interview co-pilot at AlgoAdvance.com