Minimum Number of Swaps to Make the Binary String Alternating

Minimum Number of Swaps to Make the Binary String Alternating - Problem

String Greedy Medium

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.

Input & Output

Example 1 — Basic Alternating Needed

$ Input: s = "111"

› Output: -1

💡 Note: Cannot make alternating: need equal count of 0s and 1s (±1), but have 3 ones and 0 zeros

Example 2 — One Swap Needed

$ Input: s = "1110"

› Output: 1

💡 Note: Can swap to get "1010" (pattern starting with 1) or "0101" (pattern starting with 0). Pattern "1010" needs 1 swap: position 2 and 3

Example 3 — Already Alternating

$ Input: s = "010"

› Output: 0

💡 Note: String is already alternating, no swaps needed

Constraints

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

Visualization

Tap to expand

Understanding the Visualization

Input Analysis

Count 0s and 1s, check if alternating possible

Pattern Matching

Compare against both possible alternating patterns

Optimal Swaps

Return minimum swaps needed

Key Takeaway

🎯 Key Insight: Only two alternating patterns exist - calculate swaps for each and pick minimum

Asked in

M Meta 12 a Amazon 8 G Google 6

The key insight is that only two alternating patterns exist: "010101..." and "101010...". We calculate the minimum swaps needed for each valid pattern and return the smaller value. Best approach uses greedy comparison of both patterns. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Swaps	O(n! × n)	O(n)	Try all possible swaps until string becomes alternating
Greedy - Compare Two Target Patterns	O(n)	O(1)	Calculate swaps needed for both alternating patterns and choose minimum

Brute Force - Try All Swaps — Algorithm Steps

Generate all possible pairs of positions to swap
For each swap combination, check if result is alternating
Return minimum swaps found, or -1 if impossible

Visualization

Tap to expand

Step-by-Step Walkthrough

Initial String

Start with given binary string

Try Swaps

Attempt different swap combinations

Check Pattern

Verify if result is alternating

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

bool isAlternating(const char* s) {
    int len = strlen(s);
    for (int i = 0; i < len - 1; i++) {
        if (s[i] == s[i + 1]) {
            return false;
        }
    }
    return true;
}

int solution(char* s) {
    if (isAlternating(s)) return 0;
    
    int n = strlen(s);
    char* temp = (char*)malloc((n + 1) * sizeof(char));
    
    for (int swaps = 1; swaps <= (n/2 < 5 ? n/2 : 5); swaps++) {
        strcpy(temp, s);
        int swapCount = 0;
        
        for (int i = 0; i < n - 1 && swapCount < swaps; i++) {
            if (temp[i] == temp[i + 1]) {
                for (int j = i + 2; j < n; j++) {
                    if (temp[j] != temp[i]) {
                        char c = temp[i + 1];
                        temp[i + 1] = temp[j];
                        temp[j] = c;
                        swapCount++;
                        break;
                    }
                }
            }
        }
        
        if (isAlternating(temp)) {
            free(temp);
            return swaps;
        }
    }
    
    free(temp);
    return -1;
}

int main() {
    char s[100001];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    int result = solution(s);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n! × n)

Factorial combinations of swaps, each requiring O(n) to validate

⚠ Quadratic Growth

Space Complexity

O(n)

Space to store string copies during swapping attempts

⚡ Linearithmic Space

23.4K Views

Medium Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Try All Swaps — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler