/*
169. Majority Element
*/
class Solution {
public int maxScore(String s) {
if(s == null || s.length() == 0) return -1;
int count = 0;
int res = Integer.MIN_VALUE;
int findPeak = 0;
int pivot = -1;
for(int i = 0; i < s.length(); i++) {
if(s.charAt(i) == '0')
findPeak++;
else
findPeak--;
if(i != s.length() - 1 && res < findPeak) {
res = findPeak;
pivot = i;
}
}
for(int i = 0; i <= pivot; i++) {
if(s.charAt(i) == '0')
count++;
}
for(int i = pivot + 1; i < s.length(); i++) {
if(s.charAt(i) == '1')
count++;
}
return count;
}
}
/*
238. Product of Array Except Self
*/
class Solution {
public int maxScore(String s) {
int len = s.length();
int[] prefixZero = new int[len];
int[] prefixOne = new int[len];
int zeroes = 0, ones = 0;
for(int i=0; i<len; i++) {
if(s.charAt(i) == '0') {
zeroes++;
} else {
ones++;
}
prefixZero[i] = zeroes;
prefixOne[i] = ones;
}
int max = 0;
for(int i=0; i<len-1; i++){
int cntZero = prefixZero[i];
int cntOne = prefixOne[len-1]-prefixOne[i];
max = Math.max(cntZero+cntOne, max);
}
return max;
}
}