C++ LeetCode1781題解所有子字符串美麗值之和

更新時間：2022年12月16日 10:54:15 作者：LetMeFly

這篇文章主要為大家介紹了C++ LeetCode1781題解所有子字符串美麗值之和，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪

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

力扣題目鏈接：leetcode.cn/problems/su…

一個字符串的 美麗值 定義為：出現(xiàn)頻率最高字符與出現(xiàn)頻率最低字符的出現(xiàn)次數(shù)之差。

比方說，"abaacc" 的美麗值為 3 - 1 = 2 。

給你一個字符串 s ，請你返回它所有子字符串的 美麗值 之和。

示例 1：

輸入：s = "aabcb"
輸出：5
解釋：美麗值不為零的字符串包括 ["aab","aabc","aabcb","abcb","bcb"] ，每一個字符串的美麗值都為 1 。

示例 2：

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

提示：

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

方法一：前綴和

我們分別統(tǒng)計出26種字母的前綴和

這樣，我們只需要枚舉子串區(qū)間（兩重循環(huán)枚舉子串首尾），再統(tǒng)計出這個區(qū)間中，字母的最大和最小出現(xiàn)頻率，累加到答案中即可。

AC代碼

C++

class Solution {
public:
    int beautySum(string s) {
        int n = s.size();
        vector<vector<int>> prefix(26, vector<int>(n + 1));
        for (int i = 1; i <= n; i++) {
            for (int c = 0; c < 26; c++) {
                prefix[c][i] = prefix[c][i - 1];
            }
            prefix[s[i - 1] - 'a'][i]++;
        }
        int ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int M = 0, m = 1000;
                for (int c = 0; c < 26; c++) {
                    int thisC = prefix[c][j + 1] - prefix[c][i];
                    M = max(M, thisC);
                    if (thisC) {  // 不能出現(xiàn)0次
                        m = min(m, thisC);
                    }
                }
                // printf("i = %d, j = %d, M = %d, m = %d\n", i, j, M, m);  //***********
                ans += M - m;
            }
        }
        return ans;
    }
};

方法二：邊遍歷邊計算

方法一中，我們預處理使用前綴和計算出了每種元素的出現(xiàn)情況。但是每種字母的前綴和都需要O(len(s))O(len(s))O(len(s))的空間復雜度來保存

方法二中，我們不提前預處理計算出字母的出現(xiàn)情況，而是在枚舉字符串終點的同時計算。這樣，空間復雜度就減小了一個維度。

AC代碼

C++

class Solution {
public:
    int beautySum(string s) {
        int ans = 0;
        int n = s.size();
        for (int i = 0; i < n; i++) {
            int cnt[26] = {0};  // 只需要開辟O(C)的空間
            for (int j = i; j < n; j++) {
                cnt[s[j] - 'a']++;  // 枚舉子串終點的同時統(tǒng)計元素出現(xiàn)的次數(shù)
                int M = 0, m = 1000;
                for (int d = 0; d < 26; d++) {
                    M = max(M, cnt[d]);
                    if (cnt[d])
                        m = min(m, cnt[d]);
                }
                ans += M - m;
            }
        }
        return ans;
    }
};

以上就是C++ LeetCode1781題解所有子字符串美麗值之和的詳細內(nèi)容，更多關(guān)于C++ 子字符串美麗值和的資料請關(guān)注腳本之家其它相關(guān)文章！

您可能感興趣的文章: