Skip to content

1888. Minimum Number of Flips to Make the Binary String Alternating 👍

  • Time: $O(n)$
  • Space: $O(n)$
 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
26
class Solution {
 public:
  int minFlips(string s) {
    const int n = s.length();
    // count[0][0] := the number of 0s in the even indices
    // count[0][1] := the number of 0s in the odd indices
    // count[1][0] := the number of 1s in the even indices
    // count[1][1] := the number of 1s in the odd indices
    vector<vector<int>> count(2, vector<int>(2));

    for (int i = 0; i < n; ++i)
      ++count[s[i] - '0'][i % 2];

    // min(make all 0s in the even indices + make all 1s in the odd indices,
    //     make all 1s in the even indices + make all 0s in the odd indices)
    int ans = min(count[1][0] + count[0][1], count[0][0] + count[1][1]);

    for (int i = 0; i < n; ++i) {
      --count[s[i] - '0'][i % 2];
      ++count[s[i] - '0'][(n + i) % 2];
      ans = min({ans, count[1][0] + count[0][1], count[0][0] + count[1][1]});
    }

    return ans;
  }
};

 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 minFlips(String s) {
    final int n = s.length();
    // count[0][0] := the number of 0s in the even indices
    // count[0][1] := the number of 0s in the odd indices
    // count[1][0] := the number of 1s in the even indices
    // count[1][1] := the number of 1s in the odd indices
    int[][] count = new int[2][2];

    for (int i = 0; i < n; ++i)
      ++count[s.charAt(i) - '0'][i % 2];

    // min(make all 0s in the even indices + make all 1s in the odd indices,
    //     make all 1s in the even indices + make all 0s in the odd indices)
    int ans = Math.min(count[1][0] + count[0][1], count[0][0] + count[1][1]);

    for (int i = 0; i < n; ++i) {
      --count[s.charAt(i) - '0'][i % 2];
      ++count[s.charAt(i) - '0'][(n + i) % 2];
      ans = Math.min(ans, Math.min(count[1][0] + count[0][1], count[0][0] + count[1][1]));
    }

    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
  def minFlips(self, s: str) -> int:
    n = len(s)
    # count[0][0] :=  the number of '0' in the even indices
    # count[0][1] :=  the number of '0' in the odd indices
    # count[1][0] :=  the number of '1' in the even indices
    # count[1][1] :=  the number of '1' in the odd indices
    count = [[0] * 2 for _ in range(2)]

    for i, c in enumerate(s):
      count[ord(c) - ord('0')][i % 2] += 1

    # min(make all 0s in the even indices + make all 1s in the odd indices,
    #     make all 1s in the even indices + make all 0s in the odd indices)
    ans = min(count[1][0] + count[0][1], count[0][0] + count[1][1])

    for i, c in enumerate(s):
      count[ord(c) - ord('0')][i % 2] -= 1
      count[ord(c) - ord('0')][(n + i) % 2] += 1
      ans = min(ans, count[1][0] + count[0][1], count[0][0] + count[1][1])

    return ans