cpp 解法, 执行用时: 136 ms, 内存消耗: 6.2 MB, 提交时间: 2022-12-10 13:36:54

class Solution {
public:
    int cnt[500][26];
    int beautySum(string s) {
        memset(cnt,0,500*26*4);
        for(int i =0;i<s.length();i++){
            for(int j =0;i&&j<26;j++){
                cnt[i][j] = cnt[i-1][j];
            }
            cnt[i][s[i]-'a']++;
        }
        int sum = 0;
        for(int i =0;i<s.length();i++){
            for(int j =0;j<=i;j++){
                int mx = INT_MIN,mi = INT_MAX;
                for(int k = 0;k<26;k++){  
                    int t = cnt[i][k]-(j?cnt[j-1][k]:0);
                    if(t==0)
                        continue;
                    mx = max(t,mx);
                    mi = min(t,mi);
                }
                sum+=mx-mi;
            }
        }
        return sum;
    }
};

java 解法, 执行用时: 53 ms, 内存消耗: 41.4 MB, 提交时间: 2022-12-10 13:36:16

class Solution {

    public int beautySum(String s) {
        if (s.isEmpty()) {
            return 0;
        }

        int totalSum = 0;
        char[] chs = s.toCharArray();
        for (int i = 0; i < chs.length; i++) {
            int[] counts = new int[26];
            for (int j = i; j < chs.length; j++) {
                counts[chs[j] - 'a']++;
                int max = Integer.MIN_VALUE;
                int min = Integer.MAX_VALUE;
                //26大小，相对来说就是o(1)
                for (int count : counts) {
                    if (count > 0) {
                        max = Math.max(max, count);
                        min = Math.min(min, count);
                    }
                }
                totalSum = totalSum + max - min;
            }
        }
        return totalSum;
    }
}

python3 解法, 执行用时: 2816 ms, 内存消耗: 15.2 MB, 提交时间: 2022-12-10 13:35:35

class Solution:
    def beautySum(self, s: str) -> int:
        ans = 0
        li = []
        for c in s:
            new = [0] * 26
            i = ord(c) - ord('a')
            new[i] = 1
            for counter in li:
                counter[i] += 1
                ans += max(counter) - min(k for k in counter if k)
            li.append(new)
        return ans

cpp 解法, 执行用时: 380 ms, 内存消耗: 8.5 MB, 提交时间: 2022-12-10 13:35:06

class Solution {
public:
    int beautySum(string s) {
        int n = s.size(), sum = 0;
        for(int len = 2; len <= n; ++len){
            int r = 0, l = 0, minN = INT_MAX, maxN = INT_MIN;
            vector<int> nums(26, 0); // 使用数组存储每个字符的数量
            while(r < n){ // 滑动窗口
                nums[s[r] - 'a']++;
                r++;
                if(r - l == len){
                    minN = INT_MAX;
                    maxN = INT_MIN;
                    for(int i = 0; i < 26; ++i){
                        if(nums[i] > 0){
                            minN = min(minN, nums[i]);
                            maxN = max(maxN, nums[i]);
                        }
                    }
                    sum += maxN - minN;
                    nums[s[l] - 'a']--;
                    l++;
                }
            }
        }
        return sum;
    }
};

python3 解法, 执行用时: 1884 ms, 内存消耗: 14.9 MB, 提交时间: 2022-12-10 13:34:40

from collections import Counter

class Solution:
    def beautySum(self, s: str) -> int:
        ans = 0
        for i in range(len(s)):
            count = Counter()
            for j in range(i, len(s)):
                count[s[j]] += 1
                max_value = max(count.values())
                min_value = min(count.values())
                ans += (max_value - min_value)
        return ans