Descripion

Submission

class Solution {
public:
    int largestVariance(string s) {
        int ret = 0;
        for(int i = 0; i < 26; ++i) {
            char ch1 = 'a' + i;
            for(int j = 0; j < 26; ++j) {
                if(i == j) continue;
                vector<int> arr;

                char ch2 = 'a' + j;

                for(char ch: s) {
                    if(ch == ch1) arr.push_back(1);
                    else if(ch == ch2) arr.push_back(-1);
                }

                int t = arr.size();
                if(!t) continue;
                vector<int> dp1(t);
                dp1[0] = arr[0]; 
                for(int k = 1; k < t; ++k) {
                    dp1[k] = max(dp1[k-1] + arr[k], arr[k]);
                }
                
                vector<int> dp2(t);
                dp2[t-1] = arr[t-1];

                for(int k = t - 2; k >= 0; --k) {
                    dp2[k] = max(dp2[k+1] + arr[k], arr[k]);
                }

                for(int k = 0; k < t; ++k) {
                    if(arr[k] == -1) ret = max(ret, dp1[k] + dp2[k] - arr[k]);
                }
            }
        }

        return ret;
    }
};


// [1, 1, 1, 1, {-1], 1} -1, 1, -1