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 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 <= 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;
    }
}

All Problems

All Solutions