Formatted question description: https://leetcode.ca/all/1888.html

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

## Level

Medium

## 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 alternatingThe 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 <= 10^5`

`s[i]`

is either`'0'`

or`'1'`

.

## Solution

If only type-2 operations are performed, since the alternating string can either start with 0 or 1, the minimum number of flips can be calculated for the two cases. Use `count0`

and `count1`

to represent the minimum number of flips if the alternating string starts with 0 and with 1, respectively.

If the length of `s`

is even, then any type-1 operation will not reduce the number of type-2 operations, so return the minimum of `count0`

and `count1`

.

If the length of `s`

is odd, then type-1 operations may reduce the number of type-2 operations. For `0 < i < s.length()`

, we may remove the first `i`

characters at the start of `s`

and append them to the end of `s`

. Before performing type-1 operations, for each `0 < i < s.length()`

, calculate the minimum number of type-2 operations if `s[i - 1] = s[i] = '0'`

and `s[i - 1] = s[i] = '1'`

respectively. To do this in `O(n)`

time, loop over `s`

forward and backward, and for each `0 <= i < s.length()`

, calculate the minimum number of type-2 operations needed for both `s[i] = 0`

and `s[i] = 1`

in both directions. After the values are calculated, the minimum number of type-2 operations can be calculated.

```
class Solution {
public int minFlips(String s) {
int length = s.length();
int count0 = 0, count1 = 0;
for (int i = 0; i < length; i++) {
char c = s.charAt(i);
if (c == '0') {
if (i % 2 == 0)
count1++;
else
count0++;
} else {
if (i % 2 == 0)
count0++;
else
count1++;
}
}
if (length % 2 == 0)
return Math.min(count0, count1);
int[][] dpForward = new int[length][2];
if (s.charAt(0) == '0')
dpForward[0][1] = 1;
else
dpForward[0][0] = 1;
for (int i = 1; i < length; i++) {
if (s.charAt(i) == '0') {
dpForward[i][0] = dpForward[i - 1][1];
dpForward[i][1] = dpForward[i - 1][0] + 1;
} else {
dpForward[i][0] = dpForward[i - 1][1] + 1;
dpForward[i][1] = dpForward[i - 1][0];
}
}
int[][] dpBackward = new int[length][2];
if (s.charAt(length - 1) == '0')
dpBackward[length - 1][1] = 1;
else
dpBackward[length - 1][0] = 1;
for (int i = length - 2; i >= 0; i--) {
if (s.charAt(i) == '0') {
dpBackward[i][0] = dpBackward[i + 1][1];
dpBackward[i][1] = dpBackward[i + 1][0] + 1;
} else {
dpBackward[i][0] = dpBackward[i + 1][1] + 1;
dpBackward[i][1] = dpBackward[i + 1][0];
}
}
int minCount = Math.min(count0, count1);
for (int i = 1; i < length; i++) {
int curMin = Math.min(dpForward[i - 1][0] + dpBackward[i][0], dpForward[i - 1][1] + dpBackward[i][1]);
minCount = Math.min(minCount, curMin);
}
return minCount;
}
}
```