algoadvance

Leetcode 1422. Maximum Score After Splitting a String

Problem Statement

You are given a string s of zeros and ones, and you are allowed to split the string into two non-empty substrings s1 and s2, where s1 is a prefix of s and s2 is a suffix of s. The score of the split is the number of zeros in s1 plus the number of ones in s2.

Return the maximum score that you can obtain.

Clarifying Questions

  1. Q: Is the split of the string mandatory?
    • Yes, you must split the string into two non-empty substrings.
  2. Q: Can there be leading or trailing zeros or ones in the string?
    • Yes, the string can have any arrangement of zeros and ones.
  3. Q: Is there a limit to the length of the string s?
    • For practical purposes regarding the size of the input, the length is constrained by the limits defined by the problem on LeetCode, usually up to (10^5).

Strategy

To maximize the score:

  1. Iterate over each possible split point in the string.
  2. Track the number of zeros and ones seen so far.
  3. For each split point, calculate the score (count_zeros_left + count_ones_right) and update the maximum score accordingly.

Code

Here’s the Java solution implementing the strategy:

public class Solution {
    public int maxScore(String s) {
        int n = s.length();
        int[] prefixZerosCount = new int[n];
        int[] suffixOnesCount = new int[n];
        
        // Calculate prefixZerosCount
        int countZeros = 0;
        for (int i = 0; i < n; i++) {
            if (s.charAt(i) == '0') {
                countZeros++;
            }
            prefixZerosCount[i] = countZeros;
        }
        
        // Calculate suffixOnesCount
        int countOnes = 0;
        for (int i = n - 1; i >= 0; i--) {
            if (s.charAt(i) == '1') {
                countOnes++;
            }
            suffixOnesCount[i] = countOnes;
        }
        
        // Calculate the maximum score
        int maxScore = 0;
        for (int i = 0; i < n - 1; i++) { // n-1 because we want two non-empty substrings
            int score = prefixZerosCount[i] + suffixOnesCount[i + 1];
            maxScore = Math.max(maxScore, score);
        }
        
        return maxScore;
    }
    
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.maxScore("011101")); // Output: 5
        System.out.println(solution.maxScore("00111"));  // Output: 5
        System.out.println(solution.maxScore("1111"));   // Output: 3
    }
}

Time Complexity

Overall, the solution runs in (O(n)) time complexity, where (n) is the length of the input string s. This ensures efficiency even for the upper limits of input sizes.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI