#1864

Medium

auto_awesomeGreedy choice plus invariant validation

LeetCode Problem Workspace

Minimum Number of Swaps to Make the Binary String Alternating

This problem requires finding the minimum number of swaps to make a binary string alternating or determine if it's impossible.

string greedy

Problem Statement

Given a binary string s, your task is to determine the minimum number of swaps needed to make it alternate between '0' and '1'. A string is alternating if no two adjacent characters are the same. For example, '010' and '1010' are alternating, but '0100' is not.

If it is impossible to transform the string into an alternating one through swaps, return -1. Any two characters in the string may be swapped, even if they are not adjacent.

Examples

Example 1

Input: s = "111000"

Output: 1

Swap positions 1 and 4: "111000" -> "101010" The string is now alternating.

Example 2

Input: s = "010"

Output: 0

The string is already alternating, no swaps are needed.

Example 3

Input: s = "1110"

Output: -1

Example details omitted.

Constraints

1 <= s.length <= 1000
s[i] is either '0' or '1'.

Solution Approach

Greedy Approach with Invariant Validation

A greedy strategy can be used to attempt matching the string to one of the two alternating patterns: '0101...' or '1010...'. By checking the number of mismatches with both patterns, we can calculate the minimum number of swaps required.

Balance of '0's and '1's

The string must contain an equal number of '0's and '1's for an alternating pattern to be possible. If the difference between the number of '0's and '1's exceeds 1, return -1, as it's impossible to alternate.

Optimal Swap Calculation

Once mismatches are identified, the number of swaps needed can be determined by counting the misplaced '0's and '1's that need to be swapped into the correct positions. The number of swaps is equal to the number of such misplaced characters.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity depends on the approach for checking mismatches against the two alternating patterns, with an optimal solution typically having O(n) time complexity where n is the string length. The space complexity is O(1) since no additional space is needed beyond counters and indices.

What Interviewers Usually Probe

Checks the candidate's ability to use greedy methods for string manipulation problems.
Evaluates the candidate's understanding of balancing and invariants in algorithms.
Assesses whether the candidate can validate edge cases like impossible transformations.

Common Pitfalls or Variants

Common pitfalls

Forgetting to check if the number of '0's and '1's are balanced, which would make it impossible to alternate the string.
Overcomplicating the solution by using nested loops or additional data structures where a greedy approach suffices.
Not correctly counting mismatches for both alternating patterns before calculating the swaps.

Follow-up variants

Given a larger binary string, how would your approach scale in terms of time and space complexity?
How can you optimize for different problem constraints, such as limiting the number of swaps or providing feedback on swap validity?
What happens if the string has an even number of characters, but still cannot be made alternating?

FAQ

How do I know if the binary string can be alternated?

A binary string can only be alternated if the number of '0's and '1's differ by at most 1. If the difference is greater than 1, it's impossible to alternate the string.

What are the two valid alternating binary strings?

The two valid alternating binary strings are '010101...' and '101010...', which alternate between '0' and '1'.

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

The approach involves checking the number of mismatches against the two alternating patterns and calculating the minimum swaps needed based on these mismatches.

Can any two characters in the string be swapped?

Yes, any two characters can be swapped, even if they are not adjacent, to make the string alternating.

What should I do if the string is already alternating?

If the string is already alternating, no swaps are needed, and the answer is 0.

terminal

Solution

Solution 1: Counting

First, we count the number of characters $0$ and $1$ in the string $\textit{s}$, denoted as $n_0$ and $n_1$ respectively.

1

2

3

4

5

6

7

8

9

10

11

12

class Solution:
    def minSwaps(self, s: str) -> int:
        def calc(c: int) -> int:
            return sum((c ^ i & 1) != x for i, x in enumerate(map(int, s))) // 2

        n0 = s.count("0")
        n1 = len(s) - n0
        if abs(n0 - n1) > 1:
            return -1
        if n0 == n1:
            return min(calc(0), calc(1))
        return calc(0 if n0 > n1 else 1)

Continue Practicing

#1850 minimum adjacent swaps to reach the kth smallest number #1881 maximum value after insertion #1903 largest odd number in string