We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Changes To Make Alternating Binary String

Number: 1884

Difficulty: Easy

Paid? No

Companies: Adobe, Tesla

Problem Description

Given a binary string consisting of only '0' and '1', the task is to determine the minimum number of operations required to convert the string into an alternating string, where no two adjacent characters are the same. In one operation, you can change any character from '0' to '1' or from '1' to '0'.

Key Insights

  • There are only two possible alternating patterns for a binary string: one starting with '0' (i.e., "0101...") and one starting with '1' (i.e., "1010...").
  • Compare the given string with both patterns to count the number of mismatches.
  • The minimum number of operations required is the smaller count of mismatches between the two patterns.
  • The solution requires a single pass through the string, making it efficient for the given constraints.

Space and Time Complexity

Time Complexity: O(n) where n is the length of the string, as we traverse the string once. Space Complexity: O(1) since we only use a few variables to store counts.

Solution

The approach involves iterating through the string and comparing each character to what it should be in the two possible alternating patterns. For each index, determine the expected character when the sequence starts with '0' and when it starts with '1'. Increase the mismatch count for each pattern if the character does not match the expected value. Finally, return the minimum mismatch count between the two, which represents the minimum number of operations required.

Code Solutions

# Function to compute minimum operations to make the string alternating
def minOperations(s: str) -> int:
    # Initialize the mismatch counters for two possible patterns
    cost_start_with_0 = 0  # Pattern: "0101..."
    cost_start_with_1 = 0  # Pattern: "1010..."
    
    # Loop over each character in the string
    for i, char in enumerate(s):
        # Expected character if pattern starts with '0'
        expected_char0 = '0' if i % 2 == 0 else '1'
        # Expected character if pattern starts with '1'
        expected_char1 = '1' if i % 2 == 0 else '0'
        
        # Increment the counter if the character does not match the expected for pattern starting with '0'
        if char != expected_char0:
            cost_start_with_0 += 1
        # Increment the counter if the character does not match the expected for pattern starting with '1'
        if char != expected_char1:
            cost_start_with_1 += 1
    
    # Return the minimal changes required between the two patterns
    return min(cost_start_with_0, cost_start_with_1)

# Example usage:
print(minOperations("0100"))  # Expected output: 1
← Back to All Questions