Frequency counting for an O(26 * N^2)-time

Here is the problem: https://leetcode.com/problems/sum-of-beauty-of-all-substrings/

1781. Sum of Beauty of All Substrings

Medium

The beauty of a string is the difference in frequencies between the most frequent and least frequent characters.

• For example, the beauty of "abaacc" is 3 - 1 = 2.

Given a string s, return the sum of beauty of all of its substrings.

 

Example 1:

Input: s = "aabcb"
Output: 5
Explanation: The substrings with non-zero beauty are ["aab","aabc","aabcb","abcb","bcb"], each with beauty equal to 1.

Example 2:

Input: s = "aabcbaa"
Output: 17

 

Constraints:

• 1 <= s.length <= 500
• s consists of only lowercase English letters.

Given relatively small N (500), a solution around N^2 should work. Generating all substrings is an N^2 operation. Keeping the frequency count of all lowercase characters (26) and doing brute-force per substring should be able to get the problem solved. It does become an 26*500*500 = 6.5M, but still doable as per the constraints of the problem. Code is down below, cheers, ACC.

public int BeautySum(string s)
{
    if (String.IsNullOrEmpty(s)) return 0;

    int retVal = 0;
    for (int i = 0; i < s.Length; i++)
    {
        int[] frequency = new int[26];

        for (int j = i; j < s.Length; j++)
        {
            frequency[(int)(s[j] - 'a')]++;

            int max = Int32.MinValue;
            int min = Int32.MaxValue;
            for (int k = 0; k < 26; k++)
            {
                if (frequency[k] > 0)
                {
                    max = Math.Max(max, frequency[k]);
                    min = Math.Min(min, frequency[k]);
                }
            }
            retVal += (max - min);
        }
    }

    return retVal;
}