Minimum Number of Swaps to Make the Binary String Alternating Python/Java solution

Python and Java implementations follow the same logic: count 0s and 1s, check feasibility, then compute mismatches for valid alternating patterns. Both languages implement the solution with a single pass over the string and constant extra memory.

What is the best approach for Minimum Number of Swaps to Make the Binary String Alternating?

The most efficient approach counts the number of 0s and 1s and evaluates possible alternating patterns. By scanning the string once, you count mismatches against valid patterns (0101... or 1010...). Each swap resolves two mismatches, so the result is mismatch/2. This greedy counting method runs in O(n) time with O(1) space.

Is Minimum Number of Swaps to Make the Binary String Alternating asked at Google/Amazon/Meta?

Alternating string and greedy mismatch counting problems appear frequently in interviews at large tech companies including Google, Amazon, and Meta. Variations often involve rearranging characters, validating patterns, or minimizing swaps in strings or arrays.

What data structure is used in Minimum Number of Swaps to Make the Binary String Alternating?

The problem primarily uses basic string traversal and integer counters. No complex data structure is required. The algorithm relies on counting characters and validating index parity, which fits common greedy and string processing techniques.

What is the time complexity of Minimum Number of Swaps to Make the Binary String Alternating?

The optimal solutions run in O(n) time because the string is scanned once or twice to count characters and mismatches. Space complexity remains O(1) since only counters and a few variables are used. No additional data structures proportional to input size are required.

Description Hints 2 Solution Video 13:16

1864. Minimum Number of Swaps to Make the Binary String Alternating

Q: Is Minimum Number of Swaps to Make the Binary String Alternating easy or hard?

The problem is classified as Medium difficulty on LeetCode. The challenge comes from recognizing that only two alternating patterns exist and that each swap fixes two mismatched positions. Once that observation is made, the implementation is straightforward.

Q: How to solve Minimum Number of Swaps to Make the Binary String Alternating in O(n)?

First count how many 0s and 1s exist in the string. If their difference exceeds 1, an alternating arrangement cannot be formed. Otherwise iterate through the string, compare each index with the expected value for patterns 0101... and 1010..., count mismatches, and return mismatch/2 for the valid configuration.

Medium44.1% acceptance2 companies

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 <= 1000
s[i] is either '0' or '1'.

Asked at 2 companies

Societe Generale Amazon

Topics

Greedy String

Hints open one at a time

Hint 1

Think about all valid strings of length n.

Hint 2

Try to count the mismatched positions with each valid string of length n.

13:16

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def minSwaps(self, s: str) -> int:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2Case 3

Input

"111000"

Input

"010"

Input

"1110"

Your code is saved on this device.Solution