1422. Maximum Score After Splitting a String

📝 Problem Details

• Title: {{problem_title}}
• Link: https://leetcode.com/problems/maximum-score-after-splitting-a-string/
• Difficulty: Easy
• Tags/Categories: Strings Prefix-Sum

💭What Were My Initial Thoughts?

- my intuition for this problem was incorrect / bad so i will be omitting it here 

💡 Explanation of Solution

1. track frequency of zeros and ones

2. optimal split calculation (best)
	- the variable `best` keeps track of the maximum difference between zeros and ones up to any split point
	- this difference helps maximise the score after adding the count of 1s to the right part 

3. final adjustment (best + ones)
	- after completing the loop iteration, best represents the optimal score contribution from the left part
	- to compute the final score, we add all remaining 1s from the right part, to best

⌛ Complexity Analysis

Time Complexity: O(n)
Space Complexity: O(1)

💻 Implementation of Solution

class Solution {
public:
    int maxScore(string s) {
        int ones = 0;
        int zeros = 0;
        int best = INT_MIN;
  
        for(int i=0; i < s.size()-1; i++){
            if(s[i] == '1') {
                ones++;
            }
            else {
                zeros++;
            }
            best = max(best, zeros - ones);
        }
 
        if( s[s.size() -1 ] == '1') {
            ones++;
        }
        return best + ones;
    }
};