1888. Minimum Number of Flips to Make the Binary String Alternating LeetCode Solution
In this guide, you will get 1888. Minimum Number of Flips to Make the Binary String Alternating LeetCode Solution with the best time and space complexity. The solution to Minimum Number of Flips to Make the Binary String Alternating problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Minimum Number of Flips to Make the Binary String Alternating
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”.
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'.
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(n)
1888. Minimum Number of Flips to Make the Binary String Alternating LeetCode Solution in C++
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;
}
}; /* code provided by PROGIEZ */
1888. Minimum Number of Flips to Make the Binary String Alternating LeetCode Solution in Java
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;
}
} // code provided by PROGIEZ
1888. Minimum Number of Flips to Make the Binary String Alternating LeetCode Solution in Python
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[int(c)][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[int(c)][i % 2] -= 1
count[int(c)][(n + i) % 2] += 1
ans = min(ans, count[1][0] + count[0][1], count[0][0] + count[1][1])
return ans # code by PROGIEZ
