1422. Maximum Score After Splitting a String

UnknownView on LeetCode

String

Time: O(n)

Space: O(1)

Intuition

Score = zeros in left part + ones in right part. Precompute prefix zeros and suffix ones.

Algorithm

1For each split position i (0 to n-1): score = zeros_in_s[0..i] + ones_in_s[i+1..n-1].
2Precompute suffix ones. Scan left to right counting zeros, compute score at each split.

Common Pitfalls

•Split divides s into two non-empty parts. Split at i: left is s[0..i], right is s[i+1..n-1].

1422.cs

// Approach: Single pass counting zeros on the left and tracking remaining ones on the right; max score = max(zeros + ones).
// Time: O(n) Space: O(1)

public class Solution
{
    public int MaxScore(string s)
    {
        int ans = 0;
        int zeros = 0;
        int ones = s.Count(c => c == '1');

        for (int i = 0; i + 1 < s.Length; ++i)
        {
            if (s[i] == '0')
                ++zeros;
            else
                --ones;
            ans = Math.Max(ans, zeros + ones);
        }

        return ans;
    }
}

Was this solution helpful?