Link Problem

Solution:

Because we split the string into two different continuous parts, we are able to develop an efficient O(n) algorithm.

1. Determine the number of characters '1' in the given string and store them in a variable.

2. Start traversing from the 0th to the n-2nd character.

3. At each step, if the current character is '0', we increase zero, or if it is '1', we decrease the count one variable. Finally, you can get the result by getting one plus zero

4. Return the result.

Code:

class Solution {
public:
    int maxScore(string s) {
        int res = 0, one = 0, zero = 0;

        for(char ch : s) {
            if(ch == '1') 
                ++one;
        }

        const int n = (int) s.size();
        for(int i = 0; i < n - 1; ++i) {
            if(s[i] == '0')
                ++zero;
            else
                --one;
            res = max(res, one + zero);
        }

        return res;
    }
};