力扣算法题——828.统计子串中的唯一字符

828.统计子串中的唯一字符

力扣题目：https://leetcode.cn/problems/count-unique-characters-of-all-substrings-of-a-given-string/

题目：
我们定义了一个函数 countUniqueChars(s) 来统计字符串 s 中的唯一字符，并返回唯一字符的个数。

例如：s = “LEETCODE” ，则其中 “L”, “T”,“C”,“O”,“D” 都是唯一字符，因为它们只出现一次，所以 countUniqueChars(s) = 5 。

本题将会给你一个字符串 s ，我们需要返回 countUniqueChars(t) 的总和，其中 t 是 s 的子字符串。输入用例保证返回值为 32 位整数。

注意，某些子字符串可能是重复的，但你统计时也必须算上这些重复的子字符串（也就是说，你必须统计 s 的所有子字符串中的唯一字符）。

示例 1：

输入: s = "ABC"
输出: 10
解释: 所有可能的子串为："A","B","C","AB","BC" 和 "ABC"。
     其中，每一个子串都由独特字符构成。
     所以其长度总和为：1 + 1 + 1 + 2 + 2 + 3 = 10
1
2
3
4
5

示例 2：

输入: s = "ABA"
输出: 8
解释: 除了 countUniqueChars("ABA") = 1 之外，其余与示例 1 相同。
1
2
3

示例 3：

输入：s = "LEETCODE"
输出：92
1
2

提示：
1 <= s.length <= 10^5
s 只包含大写英文字符

思路：
假设一个长度为n的字符串中第i个字母为S，且唯一，那么包含S的子串个数（贡献值）为(i - 0) * (n - i + 1)
因此我们只需将字符串按各字母且分为该字母唯一的最大子串，并计算其贡献值的和即可。

比如，我们计算"LEETCODELEETCODE"中T的贡献值时，我们将这个字符串分为"LEETCODELEE"和"CODELEETCODE"，子串中T的贡献值分别为4 * 8 和 8 * 5

Java代码

class Solution {
    public int uniqueLetterString(String s) {
        int n = s.length();
        int ans = 0;
        //计算每个字母的贡献值
        for (char i = 'A'; i <= 'Z'; i++) {
            //l,r记录字母i唯一的最大子串范围
            for (int j = 0, l = -1, r = -1; j < n; ++j) {
                if (s.charAt(j) == i){
                    l = r;
                    r = j;
                }
                ans += r - l;
            }
        }
        return ans ;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18