leetcode 828. 独特字符串

题目描述

如果一个字符在字符串 S 中有且仅有出现一次,那么我们称其为独特字符。
例如,在字符串 S = “LETTER” 中,”L” 和 “R” 可以被称为独特字符。
我们再定义 UNIQ(S) 作为字符串 S 中独特字符的个数。
那么,在 S = “LETTER” 中, UNIQ(“LETTER”) = 2。
对于给定字符串 S,计算其所有非空子串的独特字符的个数(即 UNIQ(substring))之和。
如果在 S 的不同位置上出现两个甚至多个相同的子串,那么我们认为这些子串是不同的。
考虑到答案可能会非常大,规定返回格式为:结果 mod 10 ^ 9 + 7。

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

示例 2:
输入: “ABA”
输出: 8
解释: 除了子串 UNIQ(‘ABA’) = 1,其余与示例1相同。

说明: 0 <= S.length <= 10000。

题解

首先子串的独特字符的个数和即 sum(UNIQ(substring)),可以转化为求解包含 S[i] 的子串中,S[i] 为独特字符的和即 sum(UNIQ(S[i]))
同时包含 S[i] 的子串中,可能会存在 S[i] 永远不会为独特字符的子串;
j < i && S[j] == S[i] 时,以 S[j] 开始的子串会使 S[i] 永远成不了独特字符;
k > i && S[k] == S[i] 时,以 S[k] 结尾的子串会使 S[i] 永远成不了独特字符;
所以可以去除这两种情况,在 S[j+1:k] 之间统计 UNIQ(S[i])
最终问题就变成了计算在 S[j+1:k] 之间,包含 S[i] 的子串有多少种可能,因为每个子串中 S[i] 都会是独特字符;
S[j+1:k] 之间,包含 S[i] 的子串的数量其实就等于 (i - j) * (k - i)
S[j+1:i+1], S[j+1:i+2], ..., S[j+1:k]S[j+2:i+1], S[j+2:i+2], ...., S[j+1:k],….,S[i:i+1], S[i:i+2], ...., S[i:k]

示例代码(go)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func uniqueLetterString(S string) int {
res, n := 0, len(S)
for i := 0; i < n; i++ {
j, k := 0, 0
for j = i-1; j >= 0; j-- {
if S[j] == S[i] {
break
}
}
for k = i+1; k < n; k++ {
if S[k] == S[i] {
break
}
}
res += (i - j) * (k - i)
}
return res
}