一个字符串的美丽值定义为：出现频率最高字符与出现频率最低字符的出现次数之差。

比方说，“abaacc” 的美丽值为 3 - 1 = 2 。

给你一个字符串 s ，请你返回它所有子字符串的美丽值之和。

示例 1：
输入：s = “aabcb”
输出：5
解释：美丽值不为零的字符串包括 [“aab”,“aabc”,“aabcb”,“abcb”,“bcb”] ，每一个字符串的美丽值都为 1。

示例 2：
输入：s = “aabcbaa”
输出：17

提示：
1 <= s.length <= 500
s 只包含小写英文字母。

思路

通过双指针i，j进行双层循环，能够获得字符串s所有的子字符串。

在每一次第二层循环之前，初始化一个长度为26的数组frequency，记录s[i]-s[j]组成的字符串中各字符出现的频率。

同时维护一个maxNum用于记录当前s[i]-s[j]组成的字符串中最高的字符出现频率。

在每一次子字符串获得后，获取s[i]-s[j]组成的字符串中最低的字符出现频率minNum。将maxNum和minNum的差值累加，最后得到result。

思路递推

以实例一中s=“aabcb"为例：

  • 初始i = 0,j = 0。
  • 初始化frequency数组，同时当前子字符串为"a”。
  • s[j] = ‘a’，frequency[s[j] - ‘a’] = frequency[0] = 1，maxNum = 1(a)，minNum = 1(a)，差值为0，result += 0，此时result = 0。
  • i = 0,j = 1。
  • 当前子字符串为"aa"。
  • s[j] = ‘a’，frequency[s[j] - ‘a’] = frequency[0] = 2，maxNum = 2(a)，minNum = 2(a)，差值为0，result += 0，此时result = 0。
  • i = 0,j = 2。
  • 当前子字符串为"aab"。
  • s[j] = ‘b’，frequency[s[j] - ‘a’] = frequency[1] = 1，maxNum = 2(a)，minNum = 1(b)，差值为1，result += 1，此时result = 1。
  • i = 0,j = 3。
  • 当前子字符串为"aabc"。
  • s[j] = ‘c’，frequency[s[j] - ‘a’] = frequency[2] = 1，maxNum = 2(a)，minNum = 1(b/c)，差值为1，result += 1，此时result = 2.
  • i = 0,j = 4。
  • 当前子字符串为"aabcb"。
  • s[j] = ‘b’，frequency[s[j] - ‘a’] = frequency[1] = 2，maxNum = 2(a/b)，minNum = 1(c)，差值为1，result += 1，此时result = 3.
  • i = 1,j = 1。
  • 初始化frequency数组，同时当前子字符串为"a"。
  • s[j] = ‘a’，frequency[s[j] - ‘a’] = frequency[0] = 1，maxNum = 1(a)，minNum = 1(a)，差值为0，result += 0，此时result = 3。
  • i = 1,j = 2。
  • 当前子字符串为"ab"。
  • s[j] = ‘b’，frequency[s[j] - ‘a’] = frequency[1] = 1，maxNum = 1(a)，minNum = 1(a/b)，差值为0，result += 0，此时result = 3。
  • i = 1,j = 3。
  • 当前子字符串为"abc"。
  • s[j] = ‘c’，frequency[s[j] - ‘a’] = frequency[2] = 1，maxNum = 1(a/b/c)，minNum = 1(a/b/c)，差值为0，result += 0，此时result = 3。
  • i = 1,j = 4。
  • 当前子字符串为"abcb"。
  • s[j] = ‘b’，frequency[s[j] - ‘a’] = frequency[1] = 2，maxNum = 2(b)，minNum = 1(a/c)，差值为1，result += 1，此时result = 4。
  • i = 2,j = 2。
  • 初始化frequency数组，同时当前子字符串为"b"。
  • s[j] = ‘b’，frequency[s[j] - ‘a’] = frequency[1] = 1，maxNum = 1(b)，minNum = 1(b)，差值为0，result += 0，此时result = 4。
  • i = 2,j = 3。
  • 当前子字符串为"bc"。
  • s[j] = ‘c’，frequency[s[j] - ‘a’] = frequency[2] = 1，maxNum = 1(b/c)，minNum = 1(b/c)，差值为0，result += 0，此时result = 4。
  • i = 2,j = 4。
  • 当前子字符串为"bcb"。
  • s[j] = ‘b’，frequency[s[j] - ‘a’] = frequency[1] = 2，maxNum = 2(b)，minNum = 1(c)，差值为0，result += 1，此时result = 5。
  • i = 3,j = 3。
  • 初始化frequency数组，同时当前子字符串为"c"。
  • s[j] = ‘c’，frequency[s[j] - ‘a’] = frequency[2] = 1，maxNum = 1(c)，minNum = 1(c)，差值为0，result += 1，此时result = 5。
  • i = 3,j = 4。
  • 当前子字符串为"cb"。
  • s[j] = ‘b’，frequency[s[j] - ‘a’] = frequency[1] = 1，maxNum = 1(b/c)，minNum = 1(b/c)，差值为0，result += 1，此时result = 5。
  • i = 4,j = 4。
  • 初始化frequency数组，同时当前子字符串为"b"。
  • s[j] = ‘b’，frequency[s[j] - ‘a’] = frequency[1] = 1，maxNum = 1(b)，minNum = 1(b)，差值为0，result += 1，此时result = 5。
  • 遍历结束，result最终为5。

代码实现

    public static int beautySum(String s) {
        int result = 0,length = s.length();
        for (int i = 0; i < length; i++) {
            // 记录s[i]-s[j]组成的字符串中各字符出现的频率
            int[] frequency = new int[26];
            // 记录s[i]-s[j]组成的字符串中字符出现最多的频率
            int maxNum = 0;
            for (int j = i; j < length; j++) {
                char c = s.charAt(j);
                // 更新频率
                frequency[c - 'a']++;
                // 遍历过程中直接选出当前最大的频率
                maxNum = Math.max(maxNum,frequency[c - 'a']);
                // 遍历频率数组，找出最小的频率
                int minNum = length;
                for (int k : frequency) {
                    if (k > 0){
                        minNum = Math.min(minNum,k);
                    }
                }
                // 差值累加
                result += maxNum - minNum;
            }
        }
        return result;
    }

    public static void test(){
        System.out.println(beautySum("abaacc"));
        System.out.println(beautySum("aabcb"));
        System.out.println(beautySum("aabcbaa"));
    }