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'.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.
Java
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.
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. |
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 Number of Swaps to Make the Binary String Alternating with our built-in code editor and test cases.
Practice on FleetCode