Minimum Number of Swaps to Make the Binary String Alternating Solution
Minimum Number of Swaps to Make the Binary String Alternating solution: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Minimum Number of Swaps to Make the Binary String Alternating is a medium coding problem on strings, greedy and counting, asked in Amazon and Microsoft interviews.
- Difficulty: Medium
- Topics: Strings, Greedy, Counting
- Asked at: Amazon, Microsoft
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given a binary string s. In one swap you may exchange any two characters of s — they do not have to be next to each other.
A string is alternating when no two adjacent characters are equal, like "0101" or "10101".
Return the minimum number of swaps that make s alternating, or -1 if it cannot be done.
Example 1
Input: s = "110100"
Output: 1
Explanation: Swap the first and the last character to get `"010101"`.
Example 2
Input: s = "010"
Output: 0
Explanation: Already alternating.
Example 3
Input: s = "1110"
Output: -1
Explanation: Three `1`s and one `0` can never alternate.
Constraints
1 <= s.length <= 1000s[i] is either '0' or '1'
Hints for Minimum Number of Swaps to Make the Binary String Alternating
Hint 1
Swaps never change how many
0s and1s there are. When is an alternating arrangement possible at all?Hint 2
There are only two alternating strings of a given length: one starting with
0, one starting with1. Which of them have the right counts?Hint 3
Against a feasible target, count the mismatched positions. Each swap can fix two of them — one misplaced
0and one misplaced1.
How to solve Minimum Number of Swaps to Make the Binary String Alternating
The counts decide which of the two alternating targets are reachable; against a reachable target, the answer is half the number of mismatched positions.
Approach
- Count the
1s and0s. If they differ by more than one, return-1. - For each start bit
fin {0, 1}: the targetf, 1-f, f, ...needsceil(n / 2)copies off. Skip it ifsdoes not have exactly that many. - Count positions
iwheres[i]differs from the target bit(i + f) % 2; the cost is half that count. - Return the smaller cost among the feasible targets.
Why it works
When the counts match the target, the mismatches split evenly: every position holding a 1 where a 0 belongs is balanced by one holding a 0 where a 1 belongs. One swap of such a pair fixes two mismatches, and no swap can fix more than two, so mismatches / 2 swaps are both enough and necessary. When n is even both targets are feasible and we take the cheaper one; when n is odd only the target starting with the majority bit is feasible.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- Swaps are between any two positions, not adjacent ones — this is not a bubble-sort distance.
- For odd
nonly one target is feasible; computing the other gives a wrong (smaller) answer. - The mismatch count against a feasible target is always even; dividing by two is exact.
Reference solution
Python
def minSwaps(s: str) -> int:
n = len(s)
ones = s.count("1")
zeros = n - ones
if abs(ones - zeros) > 1:
return -1
best = -1
for f in (0, 1):
have = zeros if f == 0 else ones
if have != (n + 1) // 2:
continue
miss = 0
for i, ch in enumerate(s):
if int(ch) != (i + f) % 2:
miss += 1
if best == -1 or miss // 2 < best:
best = miss // 2
return bestJava
public static int minSwaps(String s) {
int n = s.length(), ones = 0;
for (int i = 0; i < n; i++) if (s.charAt(i) == '1') ones++;
int zeros = n - ones;
if (Math.abs(ones - zeros) > 1) return -1;
int best = -1;
for (int f = 0; f < 2; f++) {
int have = f == 0 ? zeros : ones;
if (have != (n + 1) / 2) continue;
int miss = 0;
for (int k = 0; k < n; k++) if (s.charAt(k) - '0' != (k + f) % 2) miss++;
if (best == -1 || miss / 2 < best) best = miss / 2;
}
return best;
}C++
int minSwaps(string s) {
int n = s.size(), ones = 0;
for (char ch : s) if (ch == '1') ones++;
int zeros = n - ones;
if (abs(ones - zeros) > 1) return -1;
int best = -1;
for (int f = 0; f < 2; f++) {
int have = f == 0 ? zeros : ones;
if (have != (n + 1) / 2) continue;
int miss = 0;
for (int k = 0; k < n; k++) if (s[k] - '0' != (k + f) % 2) miss++;
if (best == -1 || miss / 2 < best) best = miss / 2;
}
return best;
}JavaScript
var minSwaps = function(s) {
var n = s.length, ones = 0;
for (var i = 0; i < n; i++) if (s[i] === "1") ones++;
var zeros = n - ones;
if (Math.abs(ones - zeros) > 1) return -1;
var best = -1;
for (var f = 0; f < 2; f++) {
var have = f === 0 ? zeros : ones;
if (have !== Math.floor((n + 1) / 2)) continue;
var miss = 0;
for (var k = 0; k < n; k++) if (s.charCodeAt(k) - 48 !== (k + f) % 2) miss++;
if (best === -1 || miss / 2 < best) best = miss / 2;
}
return best;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Greedy Algorithms