力扣(LeetCode)1781. 所有子字符串美丽值之和(C++)

模拟 & 哈希集合

使用哈希集合，开字符集，下标对应小写字母顺序，值对应字符出现次数。 所有子字符串，根据示例看出，是连续子字符串。那么枚举起点，再枚举子字符串长度，就是所有连续子字符串。在枚举过程中，维护区间的字符出现次数（哈希集合）。计算美丽值，只用遍历哈希集合，维护出现最多次数和最少次数。统计美丽值，即为所求。

class Solution {
          
   
public:
    int beautySum(string s) {
          
   
        int ans = 0;
        for(int i = 0 ;i < s.size() ; i++){
          
   
            int cnt[26] = {
          
   0};
            for(int j = i ;j < s.size();j++){
          
   
                int Max = 0 ,Min = 1000;
                cnt[s[j]-a]++;
                for(char ch = a;ch<=z;ch++)
                    if(cnt[ch-a]){
          
   
                        Max = max (Max,cnt[ch-a]);
                        Min = min (Min,cnt[ch-a]);
                    }
                ans += Max - Min;
            }
        }
        return ans;
    }
};

1. 时间复杂度 : O ( n 2 × ∣ C ∣ ) O(n^2 imes |C|) O(n2×∣C∣) ， n n n 是字符串长度， ∣ C ∣ |C| ∣C∣ 是字符集大小，枚举所有子字符串的的时间复杂度 O ( n 2 ) O(n^2) O(n2) ，计算美丽值的时间复杂度 O ( ∣ C ∣ ) O(|C|) O(∣C∣) ，二者是乘积关系，总时间复杂度 O ( n 2 × ∣ C ∣ ) O(n^2 imes |C|) O(n2×∣C∣) 。
2. 空间复杂度 : O ( ∣ C ∣ ) O(|C|) O(∣C∣) ， 哈希集合的空间复杂度 O ( ∣ C ∣ ) O(|C|) O(∣C∣) 。

AC

致语

理解思路很重要 读者有问题请留言，清墨看到就会回复的。