README.md

1781. 所有子字符串美丽值之和

English Version

题目描述

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

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

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

 

示例 1：

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

示例 2：

输入：s = "aabcbaa"
输出：17

 

提示：

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

解法

计数器实现。s[i, j] 的 counter 可用于计算 s[i, j + 1]。

Python3

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

Java

class Solution {

    public int beautySum(String s) {
        int ans = 0;
        int n = s.length();
        for (int i = 0; i < n; ++i) {
            int[] counter = new int[26];
            for (int j = i; j < n; ++j) {
                ++counter[s.charAt(j) - 'a'];
                int mi = 1000;
                int mx = 0;
                for (int v : counter) {
                    if (v > 0) {
                        mi = Math.min(mi, v);
                        mx = Math.max(mx, v);
                    }
                }
                ans += mx - mi;
            }
        }
        return ans;
    }
}

C++

class Solution {
public:
    int beautySum(string s) {
        int ans = 0;
        int n = s.size();
        for (int i = 0; i < n; ++i)
        {
            vector<int> counter(26);
            for (int j = i; j < n; ++j)
            {
                ++counter[s[j] - 'a'];
                int mi = 1000;
                int mx = 0;
                for (int v : counter)
                {
                    if (v)
                    {
                        mi = min(mi, v);
                        mx = max(mx, v);
                    }
                }
                ans += mx - mi;
            }
        }
        return ans;
    }
};

Go

func beautySum(s string) int {
	ans, n := 0, len(s)
	for i := 0; i < n; i++ {
		counter := make([]int, 26)
		for j := i; j < n; j++ {
			counter[s[j]-'a']++
			mi, mx := 1000, 0
			for _, v := range counter {
				if v > 0 {
					mi = min(mi, v)
					mx = max(mx, v)
				}
			}
			ans += mx - mi
		}
	}
	return ans
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

...