英伟达超苹果
昨夜美股收盘，英伟达（NVDA）股价来到了 1224.4 美元，总市值突破 3 万亿美元，超越苹果（AAPL），成为仅次于微软（总市值 3.15 万亿美元）的全球第二大公司。
英伟达今年累计上涨超 147%，去年上涨 239%。
通常坐上一次火箭，就能成就一家百亿规模的独角兽公司，而英伟达是坐了三次火箭的神奇公司。
游戏 -> 虚拟货币（挖矿）-> AI。
得益于此，英伟达联合的创始人兼首席执行官，黄仁勋也因此成为《福布斯》全球富豪榜上第 16 位资产超过千亿美元的"超级富豪"之一。
...
回归主线。
来一道与之前读者投稿的「字节跳动（抖音 UG）社招一面」相关的变形题。
题目描述
平台：LeetCode
题号：828
我们定义了一个函数 countUniqueChars(s) 来统计字符串 s 中的唯一字符，并返回唯一字符的个数。
例如：s = "LEETCODE" ，则其中 "L", "T","C","O","D" 都是唯一字符，因为它们只出现一次，所以 countUniqueChars(s) = 5。
本题将会给你一个字符串 s ，我们需要返回 countUniqueChars(t) 的总和，其中 t 是 s 的子字符串。
输入用例保证返回值为 32 位整数。
注意，某些子字符串可能是重复的，但你统计时也必须算上这些重复的子字符串（也就是说，你必须统计 s 的所有子字符串中的唯一字符）。
示例 1：
代码语言：javascript复制输入: s = "ABC"
输出: 10
解释: 所有可能的子串为："A","B","C","AB","BC" 和 "ABC"。
其中，每一个子串都由独特字符构成。
所以其长度总和为：1 1 1 2 2 3 = 10
示例 2：
代码语言：javascript复制输入: s = "ABA"
输出: 8
解释: 除了 countUniqueChars("ABA") = 1 之外，其余与示例 1 相同。
示例 3：
代码语言：javascript复制输入：s = "LEETCODE"
输出：92
提示：
s只包含大写英文字符
模拟 乘法原理
这道题和 907. 子数组的最小值之和 如出一辙，只不过无须考虑运用「单调栈」。
原问题为求所有子数组的唯一字符数量和，其可等价为求每个
对答案的贡献，即每个
可作为多少个子数组的唯一元素。
假定我们能预处理出两数组 l 和 r 分别代表
作为子数组唯一字符时，其所能到达的最远两端：
l[i] = a代表下标
为
能够作为子数组唯一字符时的最远左边界，即为
左边第一个与
值相同的位置（若不存在，则为
）
r[i] = b代表跳表
为
能够作为子数组唯一字符时的最远右边界，即为
右边第一个与
值相同的位置（若不存在，则为
）
子数组左端点个数为
个，右端点个数为
个，根据乘法原理可知，子数组个数为两者乘积。
预处理 l 和 r 只需要使用遍历计数即可。
Java 代码：
代码语言：javascript复制class Solution {
public int uniqueLetterString(String s) {
char[] cs = s.toCharArray();
int n = cs.length, ans = 0;
int[] l = new int[n], r = new int[n];
int[] idx = new int[26];
Arrays.fill(idx, -1);
for (int i = 0; i < n; i ) {
int u = cs[i] - 'A';
l[i] = idx[u];
idx[u] = i;
}
Arrays.fill(idx, n);
for (int i = n - 1; i >= 0; i--) {
int u = cs[i] - 'A';
r[i] = idx[u];
idx[u] = i;
}
for (int i = 0; i < n; i ) ans = (i - l[i]) * (r[i] - i);
return ans;
}
}
C 代码：
代码语言：javascript复制class Solution {
public:
int uniqueLetterString(string s) {
int n = s.size(), ans = 0;
vector<int> l(n, -1), r(n, n);
vector<int> idx(26, -1);
for (int i = 0; i < n; i ) {
int u = s[i] - 'A';
l[i] = idx[u];
idx[u] = i;
}
fill(idx.begin(), idx.end(), n);
for (int i = n - 1; i >= 0; i--) {
int u = s[i] - 'A';
r[i] = idx[u];
idx[u] = i;
}
for (int i = 0; i < n; i ) ans = (i - l[i]) * (r[i] - i);
return ans;
}
};
Python 代码：
代码语言：javascript复制class Solution:
def uniqueLetterString(self, s: str) -> int:
n = len(s)
l, r = [-1] * n, [n] * n
idx = [-1] * 26
for i in range(n):
u = ord(s[i]) - ord('A')
l[i] = idx[u]
idx[u] = i
idx = [n] * 26
for i in range(n - 1, -1, -1):
u = ord(s[i]) - ord('A')
r[i] = idx[u]
idx[u] = i
return sum((i - l[i]) * (r[i] - i) for i in range(n))
Typescript 代码：
代码语言：javascript复制function uniqueLetterString(s: string): number {
let n = s.length, ans = 0
const l = new Array<number>(n), r = new Array<number>(n)
const idx = new Array<number>(26).fill(-1)
for (let i = 0; i < n; i ) {
const u = s.charCodeAt(i) - 65
l[i] = idx[u]
idx[u] = i
}
idx.fill(n)
for (let i = n - 1; i >= 0; i--) {
const u = s.charCodeAt(i) - 65
r[i] = idx[u]
idx[u] = i
}
for (let i = 0; i < n; i ) ans = (i - l[i]) * (r[i] - i)
return ans
};
- 时间复杂度：
- 空间复杂度：
线性 DP
另外一个实现思路是利用「动态规划」思想。
定义
为考虑以
为结尾的所有子串中的唯一字符个数。
不失一般性考虑
该如何转移：以
为结尾的子串包括在所有以
为结尾的子串结尾添加一个字符而来，以及
字符本身组成的新子串。
首先我们令
，同时使用
记录字符 x 前一次出现的下标，使用
记录字符 x 在上上次出现的下标，然后假设当前处理的字符为
，考虑
对
的影响（注意
始终为子串右端点）：
- 在子串左端点下标范围在
的子串中，
必然只出现一次（满足唯一字符要求），即可增加
个唯一字符
；
- 在子串左端点下标范围在
的子串中，原本位于
的字符在新子串中出现次数变为
次（不再满足唯一字符要求），即需减少
个唯一字符
。
综上，我们有状态转移方程：
实现上，由于
只依赖于
，因此我们无须真的创建动规数组，而只需要使用单个变量 cur 来记录当前处理到的
即可，累积所有的
即是答案。
Java 代码：
代码语言：javascript复制class Solution {
public int uniqueLetterString(String s) {
int n = s.length(), ans = 0, cur = 0;
int[] a = new int[26], b = new int[26];
Arrays.fill(a, -1); Arrays.fill(b, -1);
for (int i = 0; i < n; i ) {
int u = s.charAt(i) - 'A';
cur = i - b[u] - (b[u] - a[u]);
ans = cur;
a[u] = b[u]; b[u] = i;
}
return ans;
}
}
C 代码：
代码语言：javascript复制class Solution {
public:
int uniqueLetterString(string s) {
int n = s.length(), ans = 0, cur = 0;
vector<int> a(26, -1), b(26, -1);
for (int i = 0; i < n; i) {
int u = s[i] - 'A';
cur = i - b[u] - (b[u] - a[u]);
ans = cur;
a[u] = b[u]; b[u] = i;
}
return ans;
}
};
Python 代码：
代码语言：javascript复制class Solution:
def uniqueLetterString(self, s: str) -> int:
n, ans, cur = len(s), 0, 0
a, b = [-1] * 26, [-1] * 26
for i in range(n):
u = ord(s[i]) - ord('A')
cur = i - b[u] - (b[u] - a[u])
ans = cur
a[u], b[u] = b[u], i
return ans
TypeScript 代码：
代码语言：javascript复制function uniqueLetterString(s: string): number {
let n = s.length, ans = 0, cur = 0
const a = new Array<number>(26).fill(-1), b = new Array<number>(26).fill(-1)
for (let i = 0; i < n; i ) {
const u = s.charCodeAt(i) - 65
cur = i - b[u] - (b[u] - a[u])
ans = cur
a[u] = b[u]; b[u] = i
}
return ans
};
- 时间复杂度：
- 空间复杂度：
，其中
为字符集大小
