Jobs

Interviews

Discussions

Minimum Changes To Make Alternating Binary String

Easy

Asked by:

4 views

Topics:

Strings

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 <= 10⁴
s[i] is either '0' or '1'.

Minimum Changes To Make Alternating Binary String

Easy

Asked by:

4 views

Topics:

Strings

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 <= 10⁴
s[i] is either '0' or '1'.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum length of the binary string `s`? Are there any memory limitations?
Can the input string `s` be empty or null? If so, what should the return value be?
Are there any characters other than '0' and '1' present in the input string `s`?
If both alternating patterns require the same number of changes, is there a preferred pattern to optimize towards?
Are we concerned about integer overflow if the string `s` is extremely long?

Brute Force Solution

Approach

The brute force approach involves checking every single possible way to make the string alternate. We try forcing the string to start with a '0', then we try forcing it to start with a '1', and see which one requires fewer changes overall.

Here's how the algorithm would work step-by-step:

First, pretend the alternating string must start with a '0'.
Go through each position in the original string and count how many changes would be needed to make it match this '0'-starting pattern.
Next, pretend the alternating string must start with a '1'.
Again, go through each position in the original string and count the changes needed to match this '1'-starting pattern.
Finally, compare the number of changes needed for both the '0'-starting and '1'-starting cases.
Choose the smaller of the two numbers, because that represents the fewest changes needed to get an alternating string.

Code Implementation

def min_operations_to_alternating_binary_string(string):
    string_length = len(string)
    start_with_zero_changes = 0
    start_with_one_changes = 0

    # Calculate changes if string starts with '0'
    for index in range(string_length):
        if index % 2 == 0:
            if string[index] == '1':
                start_with_zero_changes += 1
        else:
            if string[index] == '0':
                start_with_zero_changes += 1

    # Calculate changes if string starts with '1'
    # We need to check both '0' and '1' starting patterns
    for index in range(string_length):
        if index % 2 == 0:
            if string[index] == '0':
                start_with_one_changes += 1
        else:
            if string[index] == '1':
                start_with_one_changes += 1

    # Choose the minimum number of changes between the two patterns
    minimum_changes = min(start_with_zero_changes, start_with_one_changes)

    return minimum_changes

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the string twice, once assuming the alternating string starts with '0' and another time assuming it starts with '1'. In each iteration, it checks each character in the input string of length n. Therefore, the number of operations is proportional to 2n, which simplifies to O(n).

Space Complexity

O(1) – The provided solution calculates the number of changes needed for two alternating patterns ('0'-starting and '1'-starting) by iterating through the input string. It only uses a few integer variables to keep track of the counts of changes for each pattern. Therefore, the space required is constant and independent of the input string's length, N.

Optimal Solution

Approach

The goal is to find the fewest changes needed to make a string alternate between 0 and 1. Instead of exploring all possibilities, we will consider two possible alternating patterns and count the differences from the given string for each pattern. The pattern with the fewest differences will be the optimal solution.

Here's how the algorithm would work step-by-step:

Imagine two target strings: one that starts with 0 and alternates (010101...) and another that starts with 1 and alternates (101010...).
Compare your original string to the '0-start' alternating string and count how many positions are different.
Compare your original string to the '1-start' alternating string and count how many positions are different.
Choose the smaller of the two counts. This represents the minimum number of changes needed to make your original string alternating.

Code Implementation

def min_operations_to_alternate(input_string):
    string_length = len(input_string)

    # Count differences for 0-start pattern.
    zero_start_diff_count = 0
    for i in range(string_length):
        if i % 2 == 0:
            if input_string[i] == '1':
                zero_start_diff_count += 1
        else:
            if input_string[i] == '0':
                zero_start_diff_count += 1

    # Count differences for 1-start pattern.
    one_start_diff_count = 0
    for i in range(string_length):
        if i % 2 == 0:
            if input_string[i] == '0':
                one_start_diff_count += 1
        else:
            if input_string[i] == '1':
                one_start_diff_count += 1

    # Return the minimum number of operations.
    return min(zero_start_diff_count, one_start_diff_count)

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input string of length n twice, once to compare against the '0-start' alternating pattern and once to compare against the '1-start' alternating pattern. Each comparison involves a constant-time operation. Since the number of operations grows linearly with the size of the input string, the overall time complexity is O(n).

Space Complexity

O(1) – The algorithm calculates the differences between the input string and two alternating patterns ('0-start' and '1-start') by comparing each character. It only needs to store two integer variables to keep track of the difference counts for the '0-start' and '1-start' patterns. The space used by these variables remains constant regardless of the input string's length (N), hence the auxiliary space complexity is O(1).

Edge Cases

Case	How to Handle
Empty string	Return 0 as no changes are needed to make an empty string alternating.
String of length 1	Return 0 as a single character string is already alternating.
String with all '0's	The solution should correctly calculate the number of changes needed to make it '010101...' or '101010...' and choose the minimum.
String with all '1's	The solution should correctly calculate the number of changes needed to make it '010101...' or '101010...' and choose the minimum.
Maximum length string (consider memory/performance)	The solution should be O(n) in time and O(1) in space, so should scale linearly with the length of the string within reasonable memory limits.
String is already alternating ('010101...')	The solution should correctly return 0 as no changes are needed.
String is already alternating ('101010...')	The solution should correctly return 0 as no changes are needed.
String length is even vs. odd	The code should handle both even and odd length strings correctly when comparing against '0101...' and '1010...' alternating patterns.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum length of the binary string `s`? Are there any memory limitations?
Can the input string `s` be empty or null? If so, what should the return value be?
Are there any characters other than '0' and '1' present in the input string `s`?
If both alternating patterns require the same number of changes, is there a preferred pattern to optimize towards?
Are we concerned about integer overflow if the string `s` is extremely long?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

First, pretend the alternating string must start with a '0'.
Go through each position in the original string and count how many changes would be needed to make it match this '0'-starting pattern.
Next, pretend the alternating string must start with a '1'.
Again, go through each position in the original string and count the changes needed to match this '1'-starting pattern.
Finally, compare the number of changes needed for both the '0'-starting and '1'-starting cases.
Choose the smaller of the two numbers, because that represents the fewest changes needed to get an alternating string.

Code Implementation

def min_operations_to_alternating_binary_string(string):
    string_length = len(string)
    start_with_zero_changes = 0
    start_with_one_changes = 0

    # Calculate changes if string starts with '0'
    for index in range(string_length):
        if index % 2 == 0:
            if string[index] == '1':
                start_with_zero_changes += 1
        else:
            if string[index] == '0':
                start_with_zero_changes += 1

    # Calculate changes if string starts with '1'
    # We need to check both '0' and '1' starting patterns
    for index in range(string_length):
        if index % 2 == 0:
            if string[index] == '0':
                start_with_one_changes += 1
        else:
            if string[index] == '1':
                start_with_one_changes += 1

    # Choose the minimum number of changes between the two patterns
    minimum_changes = min(start_with_zero_changes, start_with_one_changes)

    return minimum_changes

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Imagine two target strings: one that starts with 0 and alternates (010101...) and another that starts with 1 and alternates (101010...).
Compare your original string to the '0-start' alternating string and count how many positions are different.
Compare your original string to the '1-start' alternating string and count how many positions are different.
Choose the smaller of the two counts. This represents the minimum number of changes needed to make your original string alternating.

Code Implementation

def min_operations_to_alternate(input_string):
    string_length = len(input_string)

    # Count differences for 0-start pattern.
    zero_start_diff_count = 0
    for i in range(string_length):
        if i % 2 == 0:
            if input_string[i] == '1':
                zero_start_diff_count += 1
        else:
            if input_string[i] == '0':
                zero_start_diff_count += 1

    # Count differences for 1-start pattern.
    one_start_diff_count = 0
    for i in range(string_length):
        if i % 2 == 0:
            if input_string[i] == '0':
                one_start_diff_count += 1
        else:
            if input_string[i] == '1':
                one_start_diff_count += 1

    # Return the minimum number of operations.
    return min(zero_start_diff_count, one_start_diff_count)

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty string	Return 0 as no changes are needed to make an empty string alternating.
String of length 1	Return 0 as a single character string is already alternating.
String with all '0's	The solution should correctly calculate the number of changes needed to make it '010101...' or '101010...' and choose the minimum.
String with all '1's	The solution should correctly calculate the number of changes needed to make it '010101...' or '101010...' and choose the minimum.
Maximum length string (consider memory/performance)	The solution should be O(n) in time and O(1) in space, so should scale linearly with the length of the string within reasonable memory limits.
String is already alternating ('010101...')	The solution should correctly return 0 as no changes are needed.
String is already alternating ('101010...')	The solution should correctly return 0 as no changes are needed.
String length is even vs. odd	The code should handle both even and odd length strings correctly when comparing against '0101...' and '1010...' alternating patterns.