You are given a binary string s. You are allowed to perform two types of operations on the string in any sequence:
s and append it to the end of the string.s and flip its value, i.e., if its value is '0' it becomes '1' and vice-versa.Return the minimum number of type-2 operations you need to perform such that s becomes alternating.
The string is called alternating if no two adjacent characters are equal.
"010" and "1010" are alternating, while the string "0100" is not.
Example 1:
Input: s = "111000" Output: 2 Explanation: Use the first operation two times to make s = "100011". Then, use the second operation on the third and sixth elements to make s = "101010".
Example 2:
Input: s = "010" Output: 0 Explanation: The string is already alternating.
Example 3:
Input: s = "1110" Output: 1 Explanation: Use the second operation on the second element to make s = "1010".
Constraints:
1 <= s.length <= 105s[i] is either '0' or '1'.Problem Overview: You get a binary string s. You may rotate the string any number of times (move the first character to the end). After choosing a rotation, flip the minimum number of bits so the string becomes alternating (0101... or 1010...). Return the minimum flips required.
Approach 1: Greedy Pattern Comparison (O(n) time, O(1) space)
An alternating binary string can only follow two valid patterns: starting with 0 (0101...) or starting with 1 (1010...). Iterate through the string once and count mismatches against both patterns. Each mismatch represents a flip. The minimum of the two mismatch counts gives the answer if rotations were not allowed.
The challenge is that rotations change character positions. The greedy idea still helps: track mismatches relative to both patterns while scanning. This approach builds intuition about how alternating strings behave and shows why only two target patterns exist. Time complexity is O(n) and space complexity is O(1). This reasoning often appears in problems involving string pattern matching and greedy decisions.
Approach 2: Sliding Window with Rotations (O(n) time, O(n) space)
Rotations make the problem trickier because every rotation changes which indices should contain 0 or 1. Instead of physically rotating the string repeatedly, concatenate the string with itself (s + s). This simulates all rotations as contiguous substrings of length n.
Create two reference patterns of length 2n: one starting with 0 and the other starting with 1. Then slide a window of size n across the doubled string. Maintain mismatch counts between the window and each pattern. When the window grows beyond size n, subtract the contribution of the leftmost character. This is a classic sliding window technique.
For each window position, compute the flips needed for both alternating patterns and track the minimum. This effectively evaluates every rotation in linear time. The algorithm processes each character a constant number of times, giving O(n) time complexity and O(n) space for the doubled string and patterns.
Recommended for interviews: The sliding window with rotation simulation is the expected solution. Interviewers want to see the insight that rotations can be handled by doubling the string and evaluating length-n windows. Explaining the greedy mismatch counting first shows understanding of alternating patterns, but implementing the s + s sliding window demonstrates stronger algorithmic skill.
One efficient approach is to use a sliding window to determine the number of flips required for each substring of length equal to the original string.
For a binary string to be alternating, it can follow two patterns: '010101...' (starting with '0') and '101010...' (starting with '1'). We can employ a combination of the two permitted operations: character removal and appending, and character flipping, to transform the string into one of those patterns with the minimum number of flips.
This solution attempts both alternating patterns using a sliding window over a string doubled to simulate rotations. It counts mismatches for both patterns, adjusting counts when the window slides.
Python
Java
C++
C#
JavaScript
Time Complexity: O(n)
Space Complexity: O(n)
Another approach is to use a greedy strategy based on calculating mismatches directly without explicitly considering rotations. This involves calculating mismatches for two possible alternating patterns from the start and adjusting for the effect of rotations. This can be achieved by maintaining two mismatch counters for the two patterns and adjusting them based on the original string and its windowed variants.
This greedy approach initializes mismatch counts for both patterns. It calculates these mismatches over the length of the input string and then chooses the minimum of both as the answer.
Python
Java
C++
C#
JavaScript
Time Complexity: O(n)
Space Complexity: O(1)
| Approach | Complexity |
|---|---|
| Sliding Window with Rotations | Time Complexity: O(n) |
| Greedy Approach | Time Complexity: O(n) |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy Pattern Comparison | O(n) | O(1) | Useful for understanding alternating patterns when rotations are ignored or fixed |
| Sliding Window with Rotations | O(n) | O(n) | Best approach when rotations are allowed; evaluates all rotations efficiently |
Minimum Number of Flips to make Binary String Alternating - Sliding Window - Leetcode 1888 - Python • NeetCode • 55,951 views views
Watch 9 more video solutions →Practice Minimum Number of Flips to Make the Binary String Alternating with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor