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'.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.
The minOperations function calculates the number of operations needed to make the string alternating by comparing it to two alternating patterns: 010101... and 101010.... It iterates through the string and counts the mismatches for both patterns, returning the minimum of the two counts.
C++
Java
Python
C#
JavaScript
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.
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.
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.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n).
Space Complexity: O(n) for mask storage.
| Approach | Complexity |
|---|---|
| Compare to Two Patterns | Time Complexity: O(n), where n is the length of the string, due to the single pass through the string. |
| Precomputed Masks | Time Complexity: O(n). |
Minimum Number of Flips to make Binary String Alternating - Sliding Window - Leetcode 1888 - Python • NeetCode • 47,745 views views
Watch 9 more video solutions →Practice Minimum Changes To Make Alternating Binary String with our built-in code editor and test cases.
Practice on FleetCode