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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Minimum Changes To Make Alternating Binary String

Difficulty: Easy

Problem Description

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. Return the minimum number of operations needed to make s alternating.

Key Insights

  • An alternating string can start with either '0' or '1'.
  • For a string of length n, there are two possible valid alternating patterns: starting with '0' or starting with '1'.
  • We can count the number of changes needed to transform the input string into each of the two valid patterns.
  • The minimum of the two counts will be the answer.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

To solve the problem, we will create two patterns: one that starts with '0' and another that starts with '1'. We will iterate through the string and count how many characters need to be changed to match each pattern. Finally, we will return the minimum of the two counts as the result.

The data structure used is a simple iteration over the string, and the algorithm runs in linear time relative to the length of the string.

Code Solutions

def min_operations(s: str) -> int:
    n = len(s)
    count0 = count1 = 0

    for i in range(n):
        expected_char = '0' if i % 2 == 0 else '1'
        if s[i] != expected_char:
            count0 += 1

        expected_char = '1' if i % 2 == 0 else '0'
        if s[i] != expected_char:
            count1 += 1

    return min(count0, count1)
← Back to All Questions