Scale Engineer

Minimum Number of Swaps to Make the Binary String Alternating

Med
#1703Time: O(N), where N is the length of the string, as it involves a single pass.Space: O(1), as only a constant number of variables are used for counting.1 company
Patterns
Greedy
Data structures
String
Companies
Societe Generale

Prompt

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'.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach optimizes the counting method by gathering all necessary information—total counts of '0's and '1's, and the number of misplaced characters for both potential alternating patterns—in a single pass through the input string. This avoids redundant iterations and makes the implementation more compact and efficient.

Algorithm

  1. Initialize counters: ones = 0, misplaced_for_0_start = 0, and misplaced_for_1_start = 0.
  2. Iterate through the string s with index i from 0 to n-1 in a single pass.
  3. Inside the loop:
    • Increment ones if s[i] is '1'.
    • Check the character at the current index i against the two possible alternating patterns.
    • If i is an even position:
      • If s[i] is '1', it's a misplaced character for a target starting with '0'. Increment misplaced_for_0_start.
      • If s[i] is '0', it's a misplaced character for a target starting with '1'. Increment misplaced_for_1_start.
  4. After the loop, calculate zeros = n - ones.
  5. Check for impossibility: if abs(ones - zeros) > 1, return -1.
  6. Determine the result based on n's parity:
    • If n is even, return min(misplaced_for_0_start, misplaced_for_1_start).
    • If n is odd:
      • If ones > zeros, the target must start with '1'. Return misplaced_for_1_start.
      • Else, the target must start with '0'. Return misplaced_for_0_start.

Walkthrough

Instead of making separate passes, we can count everything at once. We iterate through the string a single time, keeping track of the total number of '1's, as well as the number of swaps needed for both the '0'-starting and '1'-starting alternating patterns.

The number of swaps for a target starting with '0' (0101...) is the number of '1's at even positions. The number of swaps for a target starting with '1' (1010...) is the number of '0's at even positions. We can count both of these during our single traversal.

After the loop, we have all the necessary counts. We first check if a solution is possible using the total counts of '0's and '1's. If it is, we use the pre-calculated swap counts to return the answer based on the string's length, just as in the previous approach.

class Solution {    public int minSwaps(String s) {        int n = s.length();        int ones = 0;        int misplaced_for_0_start = 0; // Counts '1's at even positions        int misplaced_for_1_start = 0; // Counts '0's at even positions         for (int i = 0; i < n; i++) {            char c = s.charAt(i);            if (c == '1') {                ones++;            }            if (i % 2 == 0) { // Check characters at even positions                if (c == '1') {                    misplaced_for_0_start++;                } else { // c == '0'                    misplaced_for_1_start++;                }            }        }         int zeros = n - ones;        if (Math.abs(ones - zeros) > 1) {            return -1;        }         if (n % 2 == 0) {            // For even length, both targets are possible.            // The number of misplaced '1's at even positions must equal misplaced '0's at even positions for the two targets.            return Math.min(misplaced_for_0_start, misplaced_for_1_start);        } else {            // For odd length, only one target is possible.            if (ones > zeros) { // Target must start with '1'                return misplaced_for_1_start;            } else { // Target must start with '0'                return misplaced_for_0_start;            }        }    }}

Complexity

Time

O(N), where N is the length of the string, as it involves a single pass.

Space

O(1), as only a constant number of variables are used for counting.

Trade-offs

Pros

  • Most efficient implementation, as it traverses the string only once.

  • Reduces constant factors and overhead associated with multiple loops.

  • Achieves optimal time and space complexity.

Cons

  • The logic within the single loop is slightly more complex, as it tracks multiple counts simultaneously.

Solutions

class Solution {public  int minSwaps(String s) {    int s0n0 = 0, s0n1 = 0;    int s1n0 = 0, s1n1 = 0;    for (int i = 0; i < s.length(); ++i) {      if ((i & 1) == 0) {        if (s.charAt(i) != '0') {          s0n0 += 1;        } else {          s1n1 += 1;        }      } else {        if (s.charAt(i) != '0') {          s1n0 += 1;        } else {          s0n1 += 1;        }      }    }    if (s0n0 != s0n1 && s1n0 != s1n1) {      return -1;    }    if (s0n0 != s0n1) {      return s1n0;    }    if (s1n0 != s1n1) {      return s0n0;    }    return Math.min(s0n0, s1n0);  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem