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 <= 104s[i] is either '0' or '1'.In LeetCode #1758: Minimum Changes To Make Alternating Binary String, the goal is to transform a binary string so that no two adjacent characters are the same. An alternating binary string can only follow two possible patterns: 010101... or 101010.... The key idea is to compare the input string against both patterns and count how many characters must be changed to match each one.
Iterate through the string and check whether each index matches the expected character for the current pattern. Maintain two counters: one for the pattern starting with '0' and another for the pattern starting with '1'. Each mismatch represents a required change. After scanning the entire string, the minimum of these two counts gives the answer.
This approach works because any valid alternating string must follow one of the two fixed patterns. The algorithm processes the string in a single pass, making it efficient with O(n) time complexity and O(1) extra space.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Compare with alternating patterns (start with '0' and '1') | O(n) | O(1) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
Think about how the final string will look like.
It will either start with a '0' and be like '010101010..' or with a '1' and be like '10101010..'
Try both ways, and check for each way, the number of changes needed to reach it from the given string. The answer is the minimum of both ways.
The aim here is to transform the given string into either "010101..." or "101010...", as these are the only two possible alternating patterns for a binary string. By comparing the given string to these patterns, we can determine the minimum number of operations required.
We create these patterns for the length of the string and then count mismatches for both patterns by iterating through the string.
Time Complexity: O(n), where n is the length of the string, due to the single pass through the string.
Space Complexity: O(1), as only a constant amount of extra space is used.
1def minOperations(s: str) -> int:
2 pattern1 = pattern2 = 0
3 for i in range(len(s)):
4
This Python function compares the input string against two possible alternating patterns by counting mismatches through a single iteration over the string. It returns the minimum operation count needed to transform the given string.
This method involves precomputing two mask strings that represent the possible alternating strings for any given length. We perform a comparison between the string and both masks, incrementing a counter for each mismatch, and outputting the smaller of the two.
Time Complexity: O(n).
Space Complexity: O(n) for mask storage.
1
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
A valid alternating binary string can only begin with either '0' or '1'. Checking both possibilities ensures we consider all valid outcomes and select the one requiring the fewest character changes.
Yes, this type of string pattern comparison problem is common in coding interviews. It tests basic string traversal, pattern recognition, and optimization thinking, which are frequently evaluated in technical interviews.
No special data structure is required for this problem. A simple iteration over the string with counters to track mismatches is sufficient. This keeps the solution efficient and easy to implement.
The optimal approach compares the given string with the two valid alternating patterns: starting with '0' (0101...) and starting with '1' (1010...). Count mismatches for both patterns in a single pass and return the minimum count. This ensures linear time with constant extra space.
In this solution, two mask strings are created to represent the two possible alternating patterns. The given string is then compared to each mask to count the number of changes required, with the minimum count being returned.