Sunday, July 9th

 Substrings and letter counts are the topics for the LeetCode problem for today

Given a string, we are tasked with finding a substring that has the largest "variance."  Here, variance is defined as the difference in letter counts between any 2 letters, e.g.:

    With input string s = "aababbb" , the substring "babbb" has a variance of of 3, because 4 b's and 1a

I opened with brute force, finding every possible substring with 2 for loops, storing in a map to avoid duplicates, calculating variances, then returning the max.  The first 2 test cases were correctly solved, affirming I understood the problem.  However, time was exceeded on a string of 421 characters.  Considering the input string could be up to 10^4 characters, a more efficient solution was needed.

An alternative is to count the frequencies of each letter, then consider all possible pairs of letters using a variation of Kidane's algorithm, which can find the maximum subarray sum in an array of integers.  

First, a nifty way to calculate character frequencies:

               vector<int> counter(26, 0);

for (char ch : s) {

counter[ch - 'a']++;

}

Then we consider each possible pairs of letters where one letter is a major and one letter a minor, meaning (k-1)^2 combinations, accomplished through a double for-loop

For each possible pair, we then iterate over the string, and increment a major_count and minor_count variable when one of the respective letters appears during the scan.  The variance is the difference between the major_count and minor_count variables.  A global_max variable is updated whenever major-minor reaches a new max.  

After all the possible letter combinations have been tried, then the global max is returned.