2272. Substring With Largest Variance

The variance of a string is defined as the largest difference between the number of occurrences of any 2 characters present in the string. Note the two characters may or may not be the same.

Given a string s consisting of lowercase English letters only, return the largest variance possible among all substrings of s.

A substring is a contiguous sequence of characters within a string

class Solution {
public:
    int largestVariance(string s) {
        int n = s.length();
        vector<int> freq(26,0);
        vector<vector<int>> dp;
        for(auto& ch : s) {
            freq[ch-'a']++;
            dp.push_back(freq);
        }
        int res = 0;
        for(int i = 0; i < 26; i++) {
            for(int j = 0; j < 26; j++) {
                if(i == j or !freq[i] or !freq[j]) continue;
                int a = 0, b = 0;
                for(int k = 0; k < n; k++) {
                    if(s[k]-'a' == i) a++;
                    if(s[k]-'a' == j) b++;
                    if(b)
                        res = max(res, a - b);
                    if(b > a and dp.back()[j] != dp[k][j]) {
                        a = b = 0;
                    }
                }
            }
        }
        return res;
    }
};