Skip to main content
Talentd

Minimum Number of Flips to Make the Binary String Alternating - Solution & Explanation

MediumStringDynamic ProgrammingGreedySliding Window23 min readAsked at: Amazon, Microsoft, Meta +2
Practice this problem

Problem Statement

You are given a binary string s. You are allowed to perform two types of operations on the string in any sequence:

  • Type-1: Remove the character at the start of the string s and append it to the end of the string.
  • Type-2: Pick any character in 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.

  • For example, the strings "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 <= 105
  • s[i] is either '0' or '1'.

Approach Overview

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.

Approach 1: Sliding Window with Rotations

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.

Code

PythonJavaC++C#JavaScript

Python

Java

C++

C#

JavaScript

Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Try this approach in the editor →

Approach 2: Greedy Approach

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.

Code

PythonJavaC++C#JavaScript

Python

Java

C++

C#

JavaScript

Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Try this approach in the editor →

Approach 3: Sliding Window

We notice that operation 1 effectively turns the string into a cycle, and operation 2 makes a substring of length n within the cycle into an alternating binary string.

Therefore, we only need to enumerate each substring of length n, calculate the cost to make it an alternating binary string, and take the minimum.

We can pre-calculate the number of differences between string s and the two types of alternating binary strings, denoted as cnt. The cost to make s into the first type of alternating binary string is cnt, and the cost to make s into the second type is n - cnt. We initialize ans = min(cnt, n - cnt).

Next, we enumerate each substring of length n and update the value of cnt. For each position i, we subtract the difference of s[i] from the first type of alternating binary string, and add the difference of s[i] to the second type. We update ans = min(ans, cnt, n - cnt).

Finally, return ans.

The time complexity is O(n), where n is the length of the string. The space complexity is O(1).

Code

PythonJavaC++GoTypeScriptRustJavaScriptC#

Python

Java

C++

Go

TypeScript

Rust

JavaScript

C#

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Sliding Window with Rotations

Time Complexity: O(n)
Space Complexity: O(n)

Greedy Approach

Time Complexity: O(n)
Space Complexity: O(1)

Sliding Window—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Greedy Pattern ComparisonO(n)O(1)Useful for understanding alternating patterns when rotations are ignored or fixed
Sliding Window with RotationsO(n)O(n)Best approach when rotations are allowed; evaluates all rotations efficiently

Video Solution

Minimum Number of Flips to make Binary String Alternating - Sliding Window - Leetcode 1888 - Python • NeetCode • 57,146 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Minimum Number of Flips to Make the Binary String Alternating easy or hard?
The problem is rated Medium on LeetCode with about a 53% acceptance rate. The main difficulty is recognizing that rotations can be simulated by doubling the string and evaluating windows, which reduces a naive O(n^2) idea to an O(n) solution.
Minimum Number of Flips to Make the Binary String Alternating Python/Java solution
Most implementations follow the sliding window with rotations approach. The algorithm builds alternating patterns, scans the doubled string, and updates mismatch counts while sliding the window. The same logic works across Python, Java, C++, C#, and JavaScript.
How to solve Minimum Number of Flips to Make the Binary String Alternating in O(n)?
Concatenate the string with itself to simulate all rotations. Build two alternating patterns of length 2n (starting with 0 and 1). Use a sliding window of size n and maintain mismatch counts for both patterns. Update counts as the window moves and track the minimum flips.
What is the best approach for Minimum Number of Flips to Make the Binary String Alternating?
The optimal approach uses a sliding window over a doubled string (s + s) to simulate all rotations. Compare each window of length n with two alternating patterns (0101... and 1010...). Track mismatches while sliding the window and keep the minimum flips. This runs in O(n) time.
Is Minimum Number of Flips to Make the Binary String Alternating asked at Google/Amazon/Meta?
This problem tests sliding window reasoning, greedy pattern matching, and string manipulation—topics frequently asked in interviews at companies like Amazon, Google, and Meta. Variations involving alternating strings and rotations appear regularly in coding interviews.
What data structure is used in Minimum Number of Flips to Make the Binary String Alternating?
The solution mainly uses string traversal with counters and a sliding window technique. Some implementations store the doubled string or pattern arrays, but no complex data structures are required beyond basic arrays and integer counters.
What is the time complexity of Minimum Number of Flips to Make the Binary String Alternating?
The optimal sliding window solution runs in O(n) time because each character is processed a constant number of times while expanding and shrinking the window. Space complexity is O(n) due to the doubled string or pattern arrays used to simulate rotations.

Ready to solve this problem?

Practice Minimum Number of Flips to Make the Binary String Alternating with our built-in code editor and test cases.

Practice on FleetCode
Previous

Minimum Operations to Make the Array Alternating