Skip to content

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

  • Time: $O(n)$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
 public:
  int minSwaps(string s) {
    const int ones = ranges::count(s, '1');
    const int zeros = s.length() - ones;
    if (abs(ones - zeros) > 1)
      return -1;
    if (ones > zeros)
      return countSwaps(s, '1');
    if (zeros > ones)
      return countSwaps(s, '0');
    return min(countSwaps(s, '1'), countSwaps(s, '0'));
  }

 private:
  int countSwaps(const string& s, char curr) {
    int swaps = 0;
    for (const char c : s) {
      if (c != curr)
        ++swaps;
      curr ^= 1;
    }
    return swaps / 2;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
  public int minSwaps(String s) {
    final int ones = (int) s.chars().filter(c -> c == '1').count();
    final int zeros = s.length() - ones;
    if (Math.abs(ones - zeros) > 1)
      return -1;
    if (ones > zeros)
      return countSwaps(s, '1');
    if (zeros > ones)
      return countSwaps(s, '0');
    return Math.min(countSwaps(s, '1'), countSwaps(s, '0'));
  }

  private int countSwaps(final String s, char curr) {
    int swaps = 0;
    for (final char c : s.toCharArray()) {
      if (c != curr)
        ++swaps;
      curr ^= 1;
    }
    return swaps / 2;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
  def minSwaps(self, s: str) -> int:
    ones = s.count('1')
    zeros = len(s) - ones
    if abs(ones - zeros) > 1:
      return -1

    def countSwaps(curr: str) -> int:
      swaps = 0
      for c in s:
        if c != curr:
          swaps += 1
        curr = chr(ord(curr) ^ 1)
      return swaps // 2

    if ones > zeros:
      return countSwaps('1')
    if zeros > ones:
      return countSwaps('0')
    return min(countSwaps('1'), countSwaps('0'))