JunyiCode
4/30/2020 - 5:43 PM

1422. Maximum Score After Splitting a String

  1. Majority Element
  2. Product of Array Except Self
/*
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;
        
    }
}