前言

  1. 从今天开始2022.12.12开始，LeetCode每日一题使用英文读题，主要是为了锻炼自己在英语方面的能力.
  2. 接下来LeetCode会暂缓，由于报名了蓝桥杯，我希望自己在蓝桥杯大赛上能有一个好成绩所以得刷一下蓝桥杯的题目.

题目

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:

1
2
3
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:

1
2
Input: s = "aabcbaa"
Output: 17

Constraints:

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

解题思路

其实题目的意思很简单，就是让我们找每个子字符串的最大频率字符和最小字符，他们相减，然后不断记录.

代码

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def beautySum(self, s: str) -> int:
        # two for loop
        # 1. Substring's left
        # 2. Substring's right
        # if Max - Min != 0, ans += Max - Min
        # counting Max and Min

        n = len(s)
        ans = 0
        for l in range(0, n - 2):
            count = [0] * 26
            for r in range(l, n):
                idx = ord(s[r]) - ord('a')
                count[idx] += 1
                Max = -inf
                Min = inf
                for x in count:
                    if x == 0: continue
                    Max = x if x > Max else Max
                    Min = x if x < Min else Min
                ans += Max - Min
        return ans

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int beautySum(string s) {
        int n = s.size();
        int ans = 0;
        for (int l = 0; l < n - 2; ++l){
            int count[26] = {0};
            for (int r = l; r < n; ++r){
                int idx = s[r] - 'a';
                ++count[idx];
                int Max = INT_MIN;
                int Min = INT_MAX;
                for (int x: count){
                    if (x == 0) continue;
                    Max = max(Max, x);
                    Min = min(Min, x);
                }
                ans += Max - Min;
            }
        }
        return ans;
    }
};

Go

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
func beautySum(s string) int {
    var n int = len(s)
    var res int =0
    for i:=0;i<n;i++{
        countVec := make([]int,26)
        for j:=i;j<n;j++{
            index := int(s[j]-'a')
            countVec[index]++
            minVal := math.MaxInt32
            maxVal := math.MinInt32
            for k:=0;k<26;k++{
                if countVec[k]==0{
                    continue
                }
                minVal=min(minVal,countVec[k])
                maxVal=max(maxVal,countVec[k])
            }
            res+=maxVal-minVal
        }
    }
    return res
}
func min(a int,b int) int{
    if a<b{
        return a
    }
    return b
}
func max(a int, b int) int {
    if a>b{
        return a
    }
    return b
}