Minimum Number of Swaps to Make the Binary String Alternating - Solution & Explanation
Problem Statement
Given a binary string s, return the minimum number of character swaps to make it alternating, or -1 if it is impossible.
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.
Any two characters may be swapped, even if they are not adjacent.
Example 1:
Input: s = "111000" Output: 1 Explanation: Swap positions 1 and 4: "111000" -> "101010" The string is now alternating.
Example 2:
Input: s = "010" Output: 0 Explanation: The string is already alternating, no swaps are needed.
Example 3:
Input: s = "1110" Output: -1
Constraints:
1 <= s.length <= 1000s[i]is either'0'or'1'.
Approach Overview
Problem Overview: Given a binary string s, determine the minimum number of swaps required to transform it into an alternating string (either 0101... or 1010...). Any two characters can be swapped, not just adjacent ones.
Approach 1: Count Character Approach (O(n) time, O(1) space)
The key observation: an alternating string must follow one of two patterns. Either it starts with '0' (0101...) or with '1' (1010...). First count how many 0s and 1s exist. If the difference between counts is greater than 1, forming an alternating string is impossible. Otherwise, simulate both patterns by iterating through the string and counting mismatched positions. Each swap fixes two mismatches, so the answer becomes mismatch / 2. When counts are unequal, only one pattern is valid. This method works because swaps can rearrange characters anywhere, so only the mismatch count matters. The solution relies on simple counting and fits naturally with greedy reasoning.
Approach 2: Direct Index Validation (O(n) time, O(1) space)
Instead of counting mismatches indirectly, validate each index against the expected character. Build two candidate patterns: positions with even indices should contain one value while odd indices contain the other. Iterate through the string and track mismatches for each configuration. If the number of 0s equals the number of 1s, both patterns are valid and you choose the smaller swap count. If one character appears more often, that character must occupy the even indices of the final string. This approach explicitly checks index parity and performs constant-time comparisons during a single pass. It emphasizes positional constraints common in string manipulation problems.
Recommended for interviews: The Count Character Approach is typically expected. It quickly validates feasibility using character counts and calculates swaps using mismatch pairs in one pass. Interviewers like this solution because it shows clear reasoning about alternating patterns and greedy constraints. Explaining both candidate patterns and why each swap resolves two mismatches demonstrates strong problem decomposition.
Approach 1: Count Character Approach
In this approach, we calculate the number of '0's and '1's in the input string. Depending on this count, we can check if forming an alternating string is possible. An alternating string can only be formed if the count of '0's and '1's differ by at most 1. We then construct the possible alternating patterns '010101...' and '101010...' matching the parity of '0's and '1's count and compute the minimum swaps required to rearrange the input string to one of these patterns.
This Python solution counts the '0's and '1's in the string. If the difference in their count is greater than 1, it returns -1 indicating it's impossible to form an alternating string. Otherwise, it generates two possible alternating strings of length equal to the input string ('0101...' and '1010...') and computes how many swaps are required to convert the input string to either of these.
Complexity
Time complexity: O(n), as we traverse the string a constant number of times.
Space complexity: O(n), for constructing the pattern strings and mismatch tracking.
Approach 2: Direct Index Validation
This approach focuses on examining the index positions directly to form the alternating pattern. We maintain two lists of indices where '0' and '1' occur in the string. By comparing against the desired alternating patterns, we count how many mismatched indices exist for each potential pattern ('0101...' or '1010...') and calculate the minimum number of swaps needed.
In this C++ solution, we scan through the input string to build two alternating target disposition checks ('010...' and '101...'). For the feasible pattern (depending on the counts), mismatches are counted at even and odd indices separately. By calculating mismatches, the minimum swaps required can be determined.
Code
C++
JavaScript
Complexity
Time complexity: O(n) - single pass analysis and even/odd alternation.
Space complexity: O(1) - no extra space dependent on n.
Approach 3: Counting
First, we count the number of characters 0 and 1 in the string s, denoted as n_0 and n_1 respectively.
If the absolute difference between n_0 and n_1 is greater than 1, it is impossible to form an alternating string, so we return -1.
If n_0 and n_1 are equal, we can calculate the number of swaps needed to convert the string into an alternating string starting with 0 and starting with 1, and take the minimum value.
If n_0 and n_1 are not equal, we only need to calculate the number of swaps needed to convert the string into an alternating string starting with the character that appears more frequently.
The problem is reduced to calculating the number of swaps needed to convert the string s into an alternating string starting with character c.
We define a function calc(c), which represents the number of swaps needed to convert the string s into an alternating string starting with character c. We traverse the string s, and for each position i, if the parity of i is different from c, we need to swap the character at this position, incrementing the counter by 1. Since each swap makes two positions have the same character, the final number of swaps is half of the counter.
The time complexity is O(n), where n is the length of the string s. The space complexity is O(1).
Code
Python
Java
C++
Go
TypeScript
JavaScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Count Character Approach | Time complexity: O(n), as we traverse the string a constant number of times. |
| Direct Index Validation | Time complexity: O(n) - single pass analysis and even/odd alternation. |
| Counting | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Count Character Approach | O(n) | O(1) | Best general solution; quickly checks feasibility and computes swaps using mismatch counts |
| Direct Index Validation | O(n) | O(1) | Useful when reasoning about index parity and validating expected characters directly |
Video Solution
LeetCode Contest 241 Question 2: Minimum Number of Swaps to Make the Binary String Alternating • Coding Ninjas Webinars and Contest Editorials • 2,463 views views
Watch 6 more video solutions →Frequently Asked Questions
Is Minimum Number of Swaps to Make the Binary String Alternating easy or hard?
Minimum Number of Swaps to Make the Binary String Alternating Python/Java solution
How to solve Minimum Number of Swaps to Make the Binary String Alternating in O(n)?
What is the best approach for Minimum Number of Swaps to Make the Binary String Alternating?
Is Minimum Number of Swaps to Make the Binary String Alternating asked at Google/Amazon/Meta?
What data structure is used in Minimum Number of Swaps to Make the Binary String Alternating?
What is the time complexity of Minimum Number of Swaps to Make the Binary String Alternating?
Ready to solve this problem?
Practice Minimum Number of Swaps to Make the Binary String Alternating with our built-in code editor and test cases.
Practice on FleetCode