algoadvance

Leetcode 1422. Maximum Score After Splitting a String

Problem Statement

You are given a string s of zeros and ones. You can split the string into two non-empty substrings left and right where left is a substring of s from the start of the string to an index i (0 <= i < s.length - 1) and right is a substring of s from index i + 1 to the end of the string. The score after splitting the string is the number of zeros in left plus the number of ones in right. Return the maximum score you can achieve after splitting the string s.

Clarifying Questions

  1. Q: What is the length range of the input string s? A: The length of the input string s will be between 2 and 500.

  2. Q: Can the input string s be composed of characters other than 0 and 1? A: No, the input string s will only contain the characters 0 and 1.

  3. Q: Given that the split must be non-empty, is there a specific rule for how the minimum length of both substrings should be? A: Both substrings must be non-empty, meaning left will consist of at least one character from the start, and right will consist of at least one character from the end.

Strategy

  1. Initial Count Setup: Start by counting the total number of ones in the string, which will help in calculating the score of the right part dynamically.

  2. Iterating Through Possible Splits: Iterate through possible split points (from 1 to n-1) and calculate the score:
    • Maintain a count of zeros in the left part.
    • For every split, subtract the number of ones from the countOnesInRight as we shift the split point to the right.

  3. Score Calculation: At each split point, calculate the score by adding the number of zeros in the left part to the number of ones in the right part.

  4. Store and Compare Maximum Score: Keep track of the maximum score obtained during the iterations.

Code

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

int maxScore(string s) {
    int countOnesInRight = count(s.begin(), s.end(), '1');
    int countZerosInLeft = 0;
    int maxScore = 0;
    
    for (int i = 0; i < s.size() - 1; ++i) {
        if (s[i] == '0') {
            ++countZerosInLeft;
        } else {
            --countOnesInRight;
        }
        maxScore = max(maxScore, countZerosInLeft + countOnesInRight);
    }
    
    return maxScore;
}

// Example usage:
int main() {
    string s = "011101";
    cout << "Maximum score after splitting the string: " << maxScore(s) << endl;
    return 0;
}

Time Complexity

This approach ensures that we are handling each character in the string efficiently and calculating the maximum possible score by evaluating every potential split point exactly once.

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