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

题目链接

Leetcode.828 统计子串中的唯一字符 Rating ： 2034

题目描述

我们定义了一个函数 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

示例 2：

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

示例 3：

输入：s = “LEETCODE”
输出：92

提示：

• $1<=s.length<=10^5$
• s只包含大写英文字符

分析：动态规划

对于 s的一个子串 s[0~i-1]，我们分别计算添加 s[i]，会增加多少唯一字符a和 减少多少唯一字符b，a-b就是

此次 s[0~i-1]添加 s[i]的贡献。我们只需要对 s[0 ~ n - 1]用一样的逻辑即可。

我们下面讨论，把 A添加到 BCADEAFG的贡献。

• A本身 ； 把 A添加到 G；把 A添加到 FG；都会增加 1个唯一字符。
• 把 A添加到 AFG；把 A添加到 EAFG；把 A添加到 DEAFG； 都会减少 1个唯一字符。
• 把 A添加到 ADEAFG；把 CADEAFG添加到 BCADEAFG；把 A添加到 DEAFG； 都不会发生变化。

我们发现，当添加一个字符 s[i]时：

• 增加的贡献：i - s[i]上一次出现的位置
• 减少的贡献：s[i]上一次出现的位置 - s[i]上上一次出现的位置

我们用 pre记录 s[i]上一次出现的位置，用 prepre记录 s[i]上上一次出现的位置。

添加 s[i]后总的变化量为(i - pre[s[i]]) - (pre[s[i]] - prepre[s[i]])

我们每次都用 total维护 以 s[i]结尾的 唯一字符数量。

每次都添加到答案 ans上。

时间复杂度： $O(n)$

C++代码：

class Solution {
public:int uniqueLetterString(string s) {int n = s.size();int pre[26],prepre[26];memset(pre,-1,sizeof pre);memset(prepre,-1,sizeof prepre);int ans = 0 , total = 0;;for(int i = 0;i < n;i++){int t = s[i] - 'A';total += i - 2 * pre[t] + prepre[t];ans += total;prepre[t] = pre[t];pre[t] = i;}return ans;}
};

Java代码：

class Solution {public int uniqueLetterString(String s) {int n = s.length();int[] pre = new int[26];int[] prepre = new int[26];Arrays.fill(pre,-1);Arrays.fill(prepre,-1);int ans = 0;int total = 0;for(int i = 0;i < n;i++){int t = s.charAt(i) - 'A';total += (i - pre[t]) - (pre[t] - prepre[t]);ans += total;prepre[t] = pre[t];pre[t] = i;}return ans;}
}