Skip to content

← leetcode

Maximum Score After Splitting a String

· Easy

LeetCode problem 1422

My algorithm starts off by iterating through the entire string as it is impossible to generate a score without seeing all the characters (in my case, for s.size() = n, I recorded the score when left.size() = 1 and right.size() = n-1) Then, to find the maximum, in my case, I just iterated from index position 1 to n-1 and:

  • added 1 to my score if I saw a 0
  • subtracted 1 to my score if I saw a 1

code

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

complexity

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