1758. Minimum Changes To Make Alternating Binary String
Model: qwen2.5-coder:14b
Topics: Array,Greedy
FAANG asked: 0
Acceptance rate: 58.3%
Problem Breakdown
The problem requires us to transform a given binary string s into an alternating binary string with the minimum number of operations. An alternating binary string has no two adjacent characters that are the same. The input is a string s consisting only of ‘0’s and ‘1’s. The output should be an integer representing the minimum number of changes needed.
Inputs:
- A binary string
s.
Outputs:
- An integer representing the minimum number of operations to make
salternating.
Implicit Constraints or Tricky Edge Cases:
- If the input string is already alternating, the output should be 0.
- The length of the string can be up to 10^4, so the solution must be efficient in terms of time and space complexity.
Intuition
A brute-force approach would involve generating all possible alternating strings and comparing them with the given string to find the minimum number of changes required. However, this approach is inefficient due to its high time complexity (O(n * 2^n)).
The key insight is that there are only two possible alternating patterns for a binary string: starting with ‘0’ or starting with ‘1’. For example, for a string of length 4, the two possible alternating patterns are “0101” and “1010”. We can count the number of changes required to transform the given string into each of these patterns and return the minimum of the two counts.
Approach
- Initialize two counters:
count_start_0andcount_start_1. - Iterate through the string:
- If the current index is even, check if the character matches ‘0’ for the “0101” pattern or ‘1’ for the “1010” pattern.
- If the current index is odd, check if the character matches ‘1’ for the “0101” pattern or ‘0’ for the “1010” pattern.
- Increment the respective counter based on whether the character matches the expected value for each pattern.
- Return the minimum of
count_start_0andcount_start_1.
Complexity Analysis
- Time Complexity: O(n), where n is the length of the string. We iterate through the string once to count the changes required for both patterns.
- Space Complexity: O(1). We use a constant amount of extra space for the counters.
Solution
def minChangesToMakeAlternating(s: str) -> int:
count_start_0 = 0
count_start_1 = 0
for i, char in enumerate(s):
if i % 2 == 0:
# Even index should be '0' for "0101" pattern and '1' for "1010" pattern
if char != '0':
count_start_0 += 1
if char != '1':
count_start_1 += 1
else:
# Odd index should be '1' for "0101" pattern and '0' for "1010" pattern
if char != '1':
count_start_0 += 1
if char != '0':
count_start_1 += 1
return min(count_start_0, count_start_1)
Edge Cases Handled
- Empty String: The function will handle an empty string correctly since both counters will remain 0, and the minimum of them is 0.
- Already Alternating String: If the input string is already alternating, one of the counters will be 0, and the function will return 0.
- All ‘0’s or All ‘1’s: The function will correctly count the number of changes needed to transform the string into either “0101” or “1010”.