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


Problem Description

In this problem, we are given a binary string s which only contains '0's and '1's. Our goal is to find the minimum number of character swaps required to convert the string into an alternating binary string, where no two adjacent characters are the same. For example, "010101" and "101010" are alternating strings, but "110" is not as there are two '1's adjacent to each other.

If making the string alternating is not possible, we should return -1.

A character swap means choosing any two characters in the string (not necessarily adjacent) and exchanging their positions. The challenge is to do the minimum number of such swaps to achieve an alternating pattern.

Intuition

To arrive at the solution, we first need to understand that there are only two possible alternating patterns for any string: "010101..." or "101010...". Also, for a binary string that can be made alternating, the difference between the counts of '0's and '1's cannot be more than one. If the difference is more than one, it is impossible to form an alternating string because there would be extra characters of one type that we cannot place without creating adjacent duplicates.

With this understanding, the next insight is to count the number of misplaced '0's and '1's in both possible alternating patterns. We need to track the following:

  • s0n0: Number of '0's that are in the wrong place if we are trying to form the "010101..." pattern.
  • s0n1: Number of '1's that are in the wrong place if we are trying to form the "010101..." pattern.
  • s1n0: Number of '0's that are in the wrong place if we are trying to form the "101010..." pattern.
  • s1n1: Number of '1's that are in the wrong place if we are trying to form the "101010..." pattern.

For a valid alternating string:

  • The counts of '0's and '1's should be equal, or there should be exactly one more '0' or exactly one more '1'.
  • The numbers of misplaced '0's should equal the numbers of misplaced '1's for a given pattern. That is, s0n0 should equal s0n1 and s1n0 should equal s1n1. If they are not equal, it means we can't swap a '0' with a '1' to correct the string since there's an unequal amount to swap.

After counting, we have the following cases:

  • If both the counts of s0n0 and s0n1 aren't equal, and the counts of s1n0 and s1n1 aren't equal either, we return -1 because it's impossible to make the string alternating.
  • If s0n0 and s0n1 aren't equal, which means we can't form "010101..." pattern, we should check if we can form "101010..." pattern and return s1n0 (or s1n1 since they are equal).
  • If s1n0 and s1n1 aren't equal, meaning we can't form "101010..." pattern, we should return s0n0 (or s0n1 since they are equal).
  • If we can form both "010101..." and "101010..." patterns, we return the minimum of s0n0 and s1n0.

Therefore, by counting the number of misplaced characters and comparing them, we can determine the minimum number of swaps required. If any configuration allows for alternating characters, that minimum count is the answer. If neither does, then it is impossible to form an alternating string, and we return -1.

Learn more about Greedy patterns.

Solution Approach

The solution provided follows a simple but effective approach without the need for any complex algorithms or data structures. Here's the breakdown:

  1. Initialize four counters: s0n0, s0n1, s1n0, s1n1 to zero. These will count the number of misplaced '0's and '1's for both potential alternating patterns "010101..." (s0n0 and s0n1) and "101010..." (s1n0 and s1n1).

  2. Iterate through the string s using a for-loop and the range function, checking each character:

    • If we're at an even index (using i & 1 to check if i is odd or even), we compare the character with '0'.
      • If it's not '0', then it's in the wrong place for the "010101..." pattern, so we increment s0n0.
      • If it is a '0', then it's in the wrong place for the "101010..." pattern, so we increment s1n1.
    • If we're at an odd index, we do the reverse:
      • If the character is not '0', it's wrong for "101010..." and we increment s1n0.
      • If it is a '0', it's wrong for "010101..." and we increment s0n1.
  3. After the loop, we have the counts of misplaced '0's and '1's for both patterns. We then examine these counts:

    • If s0n0 does not equal s0n1, and s1n0 does not equal s1n1, we can't form an alternating string. We return -1.
    • If s0n0 does not equal s0n1, we know that the "010101..." pattern is not possible, but the "101010..." pattern is, so we return s1n0 (or s1n1 as they are the same).
    • Conversely, if s1n0 does not equal s1n1, we can't form "101010...", but we know "010101..." is possible, so we return s0n0 (or s0n1 since they are equal).
    • If both sets of counts are equal, meaning either pattern could be formed, we return the minimum of s0n0 and s1n0.

This approach ensures we find the minimum swaps needed for either pattern if it's possible to build an alternating string out of s. It efficiently utilizes bitwise operations and simple if-else constructs without the need for additional space, hence operating in O(n) time complexity and O(1) space complexity, where n is the length of string s.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's use a small example to illustrate the solution approach. Consider the binary string s = "1001". We want to determine the minimum number of swaps required to make this string into an alternating binary string, either "1010" or "0101".

  1. Initialize our counters: s0n0 = 0, s0n1 = 0, s1n0 = 0, s1n1 = 0.

  2. We begin iterating through the string:

    • For the first character (index 0, even), we have '1'.

      • It's not '0', so it's misplaced for the "010101..." pattern. Increment s0n0 to 1.
      • Since it's '1', it's correctly placed for the "101010..." pattern, so s1n1 remains 0.
    • For the second character (index 1, odd), we have '0'

      • It's not '1', so it's misplaced for the "101010..." pattern. Increment s1n0 to 1.
      • Since it's '0', it's correctly placed for the "010101..." pattern, so s0n1 remains 0.
    • For the third character (index 2, even), we have '0'.

      • It's correctly placed for the "010101..." pattern, so s0n0 remains 1.
      • Since it's not '1', it's misplaced for the "101010..." pattern. Increment s1n1 to 1.
    • For the fourth character (index 3, odd), we have '1'.

      • It's not '0', so it's misplaced for the "010101..." pattern. Increment s0n1 to 1.
      • Since it's '1', it's correctly placed for the "101010..." pattern, so s1n0 remains 1.
  3. After iterating, our counts are as follows: s0n0 = 1, s0n1 = 1, s1n0 = 1, s1n1 = 1.

  4. We examine our counts:

    • Since s0n0 equals s0n1, and s1n0 equals s1n1, either pattern "010101..." or "101010..." can be formed.

    • We return the minimum of s0n0 and s1n0, which is min(1, 1) = 1.

Thus, it only takes a single swap to turn the string "1001" into an alternating binary string. We can swap the second and third characters to obtain "1010" or swap the first and second characters to obtain "0101".

Solution Implementation

1class Solution:
2    def minSwaps(self, s: str) -> int:
3        # Initializing counters for each possible scenario:
4        # swaps_0_to_1 - number of swaps needed if the even-index should be '0'
5        # swaps_1_to_0 - number of swaps needed if the even-index should be '1'
6        # For the strings to be valid they should alternate '01' or '10'.
7        # If it's not possible to create a valid string, return -1.
8        swaps_0_to_1 = swaps_1_to_0 = 0
9      
10        # Iterate over each character in the string
11        for index in range(len(s)):
12            # Check if the current index is even
13            if (index % 2) == 0:
14                # If current character should be '0' on even index, but it's not
15                if s[index] != '0':
16                    swaps_0_to_1 += 1
17                # If current character should be '1' on even index, but it's '0'
18                if s[index] != '1':
19                    swaps_1_to_0 += 1
20            else:
21                # If current character should be '1' on odd index, but it's not
22                if s[index] != '1':
23                    swaps_0_to_1 += 1
24                # If current character should be '0' on odd index, but it's '1'
25                if s[index] != '0':
26                    swaps_1_to_0 += 1
27      
28        # For the swaps to be possible, the number of required swaps for both scenarios must be the same
29        # If they are not, it's impossible to create a valid string of alternate characters by swapping
30        if (swaps_0_to_1 % 2) != (swaps_1_to_0 % 2):
31            return -1
32      
33        # If the total number of swaps is equal, one of them must be even since it's impossible to have an odd number of swaps for both scenarios
34        # Return the minimum number of swaps if both are even, otherwise, return the even count since the odd count will require an extra swap that isn't possible
35        if (swaps_0_to_1 % 2) == 0:
36            return min(swaps_0_to_1, swaps_1_to_0) // 2
37        else:
38            return min(swaps_0_to_1//2, swaps_1_to_0//2)
39
1class Solution {
2    public int minSwaps(String s) {
3        // Initialize counters to track the number of swaps required for each pattern.
4        // Pattern "01" requires 'swapCountPattern01' and 'swapCountPattern10' swaps.
5        // Pattern "10" requires 'swapCountPattern10' and 'swapCountPattern01' swaps.
6        int swapCountPattern01 = 0;
7        int swapCountPattern10 = 0;
8
9        // Loop through the string to count the number of swaps needed.
10        for (int i = 0; i < s.length(); ++i) {
11            // If the index 'i' is even, we expect a '0' for pattern "01" and a '1' for pattern "10".
12            if ((i & 1) == 0) {
13                if (s.charAt(i) == '1') {
14                    swapCountPattern01 += 1;
15                } else {
16                    swapCountPattern10 += 1;
17                }
18            } else {
19                // If the index 'i' is odd, we expect a '1' for pattern "01" and a '0' for pattern "10".
20                if (s.charAt(i) == '1') {
21                    swapCountPattern10 += 1;
22                } else {
23                    swapCountPattern01 += 1;
24                }
25            }
26        }
27
28        // If the number of swaps needed for both patterns is not the same, it's impossible to achieve the pattern.
29        if (swapCountPattern01 != swapCountPattern10) {
30            return -1;
31        }
32
33        // If only one pattern is possible, return the number of swaps needed for that pattern.
34        if (swapCountPattern01 != swapCountPattern10) {
35            return swapCountPattern10;
36        }
37        // If both patterns are possible, return the minimum number of swaps.
38        return Math.min(swapCountPattern01, swapCountPattern10);
39    }
40}
41
1#include <string>
2#include <algorithm>
3
4/**
5 * Determines the minimum number of swaps to make a binary string alternating.
6 * It only considers valid scenarios where the number of 1's and 0's differ by at most one.
7 * 
8 * @param binaryString - The binary string to be processed.
9 * @return The minimum number of swaps, or -1 if not possible.
10 */
11int minSwaps(const std::string& binaryString) {
12    const int length = binaryString.length();
13    // Count the number of '1's.
14    const int numberOfOnes = std::count(binaryString.begin(), binaryString.end(), '1');
15    // Calculate the number of '0's directly.
16    const int numberOfZeros = length - numberOfOnes;
17    int minCount = INT_MAX; // Use maximum integer to initialize minimum count.
18    const int halfLength = length / 2;
19
20    // Case for strings that should start with '1' (e.g., '1010' or '101').
21    if (numberOfOnes == (length + 1) / 2 && numberOfZeros == length / 2) {
22        int currentSwapCount = 0; // Swaps needed for current iteration.
23        for (int i = 0; i < length; i++) {
24            if (i % 2 == 0 && binaryString[i] != '1') {
25                currentSwapCount++;
26            }
27        }
28        minCount = std::min(minCount, currentSwapCount);
29    }
30
31    // Case for strings that should start with '0' (e.g., '0101' or '010').
32    if (numberOfZeros == (length + 1) / 2 && numberOfOnes == length / 2) {
33        int currentSwapCount = 0; // Swaps needed for current iteration.
34        for (int i = 0; i < length; i++) {
35            if (i % 2 == 0 && binaryString[i] != '0') {
36                currentSwapCount++;
37            }
38        }
39        minCount = std::min(minCount, currentSwapCount);
40    }
41
42    // If no valid scenario was found, return -1; otherwise, return the minimum swap count found.
43    return minCount == INT_MAX ? -1 : minCount;
44}
45
1/**
2 * Determines the minimum number of swaps to make a binary string alternating.
3 * It only considers valid scenarios where the number of 1's and 0's differ by at most one.
4 * 
5 * @param {string} binaryString - The binary string to be processed.
6 * @return {number} - The minimum number of swaps, or -1 if not possible.
7 */
8function minSwaps(binaryString: string): number {
9    const length: number = binaryString.length;
10    const numberOfOnes: number = Array.from(binaryString).reduce((accumulated, current) => parseInt(current) + accumulated, 0);
11    const numberOfZeros: number = length - numberOfOnes;
12    let minCount: number = Infinity;
13    const halfLength: number = length / 2;
14
15    // Case for strings that should start with '1' (e.g. '1010' or '101')
16    if (numberOfOnes === Math.ceil(halfLength) && numberOfZeros === Math.floor(halfLength)) {
17        let currentSwapCount: number = 0; // Swaps needed for current iteration
18        for (let i = 0; i < length; i++) {
19            if (i % 2 === 0 && binaryString.charAt(i) !== '1') currentSwapCount++;
20        }
21        minCount = Math.min(minCount, currentSwapCount);
22    }
23
24    // Case for strings that should start with '0' (e.g. '0101' or '010')
25    if (numberOfZeros === Math.ceil(halfLength) && numberOfOnes === Math.floor(halfLength)) {
26        let currentSwapCount: number = 0; // Swaps needed for current iteration
27        for (let i = 0; i < length; i++) {
28            if (i % 2 === 0 && binaryString.charAt(i) !== '0') currentSwapCount++;
29        }
30        minCount = Math.min(minCount, currentSwapCount);
31    }
32
33    // If no valid scenario was found, return -1, otherwise return the minimum swap count found
34    return minCount === Infinity ? -1 : minCount;
35}
36

Time and Space Complexity

Time Complexity

The given code iterates through the string s once, which means that the loop runs for n iterations, where n is the length of the string s. Within each iteration of the loop, the code performs a constant number of operations, such as comparison, bitwise AND, and increment operations, all of which take constant O(1) time. Therefore, the time complexity of the entire function is directly proportional to the length of the string, which gives us a time complexity of O(n).

Space Complexity

Regarding space complexity, the code allocates a constant amount of extra space. It uses four integer variables s0n0, s0n1, s1n0, and s1n1 to keep track of counts, no matter how large the input string s is. Since these variables do not depend on the size of the input, and no other significant space is used (no dynamic data structures or arrays are allocated), the space complexity is constant, O(1).

Learn more about how to find time and space complexity quickly using problem constraints.


Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

You are given an array of intervals where intervals[i] = [start_i, end_i] represent the start and end of the ith interval. You need to merge all overlapping intervals and return an array of the non-overlapping intervals that cover all the intervals in the input.


Recommended Readings

Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

Coding Interview Strategies

Dive into our free, detailed pattern charts and company guides to understand what each company focuses on.

See Patterns

🪄