所有子字符串美丽值之和 图解题解

美丽值到底怎么算，这题要把哪些子串的美丽值相加

先说美丽值怎么来。一个字符串的美丽值，是它里面出现次数最多的字符的次数，减去出现次数最少、但至少出现过一次的字符的次数。题目给你字符串 s，要求把 s 的每一个连续子字符串的美丽值都算出来，再全部加起来。拿题面 s='aabcb' 来说，答案是 5；再看一段 'abaacc'，里面 a 出现 3 次最多、b 出现 1 次最少，它的美丽值就是 3 减 1 等于 2。

把每个子串都重新数一遍字符，代价高在哪

长度 n 的字符串，连续子串大约有 n²/2 个，这个数量绕不过去——答案就是要对每一个子串各算一次美丽值。真正贵的是每段的处理：如果对着一个子串，从它的左端到右端把字符重新数一遍，再取最高频和最低频，单个子串就要花和它长度成正比的时间，全部加起来是 O(n³)。字符串稍微一长，这层重复计数就把时间拖垮了。

右端每多接一个字符，为什么计数只需要动一格

相邻两个子串只差最右边那一个字符。把左端钉住不动，右端每往右挪一格，新的子串只比上一个子串在右边多出一个字符，前面那些字符的计数一个都没变。于是不必从头重数，只要把新进来的这个字符的计数加一，就得到了新子串的完整计数——这种每步只改动新增那一格、别的照旧的做法叫增量维护。每扩一格后，在当前计数里取最高频减最低频，就是这一段的美丽值。要留意最低频只在真正出现过的字符里取，计数还是 0 的字母不能算进来。

固定左端、右端逐格扩，整个流程怎么跑

外层从下标 0 开始，依次让每个位置当一次子串的左端；每换一个新左端，就把计数清空。内层让右端从当前左端出发，一格一格扩到字符串末尾，每扩到一个字符就把它的计数加一，再取当前计数里的最高频减最低频，累加进答案。左端走遍所有位置，所有子串就都被覆盖了一遍，累加出来的就是总美丽值。

aabcb 里哪几段子串真有美丽值

左端钉在下标 0：子串 'a'、'aa' 里字符次数都相等，美丽值都是 0；扩到 'aab' 时 a 两次、b 一次，2 减 1 得 1；'aabc'、'aabcb' 里仍是最高 2、最低 1，各得 1，这一轮共加 3。左端挪到下标 1：'a'、'ab'、'abc' 全是 0，'abcb' 里 b 两次、a 和 c 各一次，得 1。左端到下标 2：'b'、'bc' 是 0，'bcb' 得 1。左端在下标 3、4 起头的 'c'、'cb'、'b' 都是 0。有贡献的正好是 'aab' 'aabc' 'aabcb' 'abcb' 'bcb' 五段，加起来是 5。

求最低频，先跳过计数为 0 的字母

这套做法时间是 O(n²·26)、空间 O(1)，计数最多占 26 个格子。有几处容易出错。用定长 26 的数组存计数时，那些没在子串里出现的字母还挂着 0，求最低频要跳过这些 0，只在计数大于 0 的字母里取最小；忘了跳过，最低频永远是 0，美丽值就错等于最高频，总和整个偏大。右端扩格必须增量加一，图省事从头重数会把复杂度推回 O(n³)。还有单字符、以及整段同一个字符的子串，它们的美丽值本来就是 0，照常参与累加即可，加 0 不影响结果，特意挑出来跳过反而多此一举。

Python

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class Solution:
    def beautySum(self, s: str) -> int:
        ans, n = 0, len(s)
        for i in range(n):
            cnt = Counter()
            for j in range(i, n):
                cnt[s[j]] += 1
                ans += max(cnt.values()) - min(cnt.values())
        return ans

C++

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
    int beautySum(string s) {
        int ans = 0;
        int n = s.size();
        int cnt[26];
        for (int i = 0; i < n; ++i) {
            memset(cnt, 0, sizeof cnt);
            for (int j = i; j < n; ++j) {
                ++cnt[s[j] - 'a'];
                int mi = 1000, mx = 0;
                for (int& v : cnt) {
                    if (v > 0) {
                        mi = min(mi, v);
                        mx = max(mx, v);
                    }
                }
                ans += mx - mi;
            }
        }
        return ans;
    }
};

Java

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