Question

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

中文文档

Description

You are given a binary string s. You are allowed to perform two types of operations on the string in any sequence:

• Type-1: Remove the character at the start of the string s and append it to the end of the string.
• Type-2: Pick any character in s and flip its value, i.e., if its value is '0' it becomes '1' and vice-versa.

Return _the minimum number of type-2 operations you need to perform_ _such that _s _becomes alternating._

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.

 

Example 1:

Input: s = "111000"
Output: 2
Explanation: Use the first operation two times to make s = "100011".
Then, use the second operation on the third and sixth elements to make s = "101010".

Example 2:

Input: s = "010"
Output: 0
Explanation: The string is already alternating.

Example 3:

Input: s = "1110"
Output: 1
Explanation: Use the second operation on the second element to make s = "1010".

 

Constraints:

• 1 <= s.length <= 105
• s[i] is either '0' or '1'.

Solutions

Solution 1

class Solution:
  def minFlips(self, s: str) -> int:
    n = len(s)
    target = "01"
    cnt = sum(c != target[i & 1] for i, c in enumerate(s))
    ans = min(cnt, n - cnt)
    for i in range(n):
      cnt -= s[i] != target[i & 1]
      cnt += s[i] != target[(i + n) & 1]
      ans = min(ans, cnt, n - cnt)
    return ans

class Solution {
  public int minFlips(String s) {
    int n = s.length();
    String target = "01";
    int cnt = 0;
    for (int i = 0; i < n; ++i) {
      if (s.charAt(i) != target.charAt(i & 1)) {
        ++cnt;
      }
    }
    int ans = Math.min(cnt, n - cnt);
    for (int i = 0; i < n; ++i) {
      if (s.charAt(i) != target.charAt(i & 1)) {
        --cnt;
      }
      if (s.charAt(i) != target.charAt((i + n) & 1)) {
        ++cnt;
      }
      ans = Math.min(ans, Math.min(cnt, n - cnt));
    }
    return ans;
  }
}

class Solution {
public:
  int minFlips(string s) {
    int n = s.size();
    string target = "01";
    int cnt = 0;
    for (int i = 0; i < n; ++i) {
      if (s[i] != target[i & 1]) {
        ++cnt;
      }
    }
    int ans = min(cnt, n - cnt);
    for (int i = 0; i < n; ++i) {
      if (s[i] != target[i & 1]) {
        --cnt;
      }
      if (s[i] != target[(i + n) & 1]) {
        ++cnt;
      }
      ans = min({ans, cnt, n - cnt});
    }
    return ans;
  }
};

func minFlips(s string) int {
  n := len(s)
  target := "01"
  cnt := 0
  for i := range s {
    if s[i] != target[i&1] {
      cnt++
    }
  }
  ans := min(cnt, n-cnt)
  for i := range s {
    if s[i] != target[i&1] {
      cnt--
    }
    if s[i] != target[(i+n)&1] {
      cnt++
    }
    ans = min(ans, min(cnt, n-cnt))
  }
  return ans
}

function minFlips(s: string): number {
  const n = s.length;
  const target = '01';
  let cnt = 0;
  for (let i = 0; i < n; ++i) {
    if (s[i] !== target[i & 1]) {
      ++cnt;
    }
  }
  let ans = Math.min(cnt, n - cnt);
  for (let i = 0; i < n; ++i) {
    if (s[i] !== target[i & 1]) {
      --cnt;
    }
    if (s[i] !== target[(i + n) & 1]) {
      ++cnt;
    }
    ans = Math.min(ans, cnt, n - cnt);
  }
  return ans;
}