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'.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.
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.
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.
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.
C++
JavaScript
Time complexity: O(n) - single pass analysis and even/odd alternation.
Space complexity: O(1) - no extra space dependent on n.
| 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. |
| 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 |
LeetCode Contest 241 Question 2: Minimum Number of Swaps to Make the Binary String Alternating • Coding Ninjas Webinars and Contest Editorials • 2,453 views views
Watch 5 more video solutions →Practice Minimum Number of Swaps to Make the Binary String Alternating with our built-in code editor and test cases.
Practice on FleetCode