Minimum Number of Flips to Make the Binary String Alternating
Medium
Watch on YouTube ↗Solution
class Solution {
public int minFlips(String s) {
String str = s + s; // O(n)
int n = s.length();
int ans = Integer.MAX_VALUE;
int onestart = 0, zerostart = 0;
for(int i=0; i<2*n; i++) {
// O(2*n)
char ch = str.charAt(i);
if(i%2==0) {
if(ch=='0')
onestart++;
else zerostart++;
}
else {
if(ch=='0')
zerostart++;
else onestart++;
}
if(i>=n-1) {
ans = Math.min(ans, Math.min(zerostart, onestart));
int prev = i-n+1;
char pch = str.charAt(prev);
if(prev%2==0) {
if(pch=='0')
onestart--;
else zerostart--;
}
else {
if(pch=='0')
zerostart--;
else onestart--;
}
}
}
return ans;
}
}
/*
type 1 -
1 1 1 0
1 1 0 1
1 0 1 1
0 1 1 1
s + s
1 1 1 0 1 1 1 0
*/