题目如下:
A character is unique in string
S
if it occurs exactly once in it.For example, in string
S = "LETTER"
, the only unique characters are"L"
and"R"
.Let's define
UNIQ(S)
as the number of unique characters in stringS
.For example,
UNIQ("LETTER") = 2
.Given a string
S
with only uppercases, calculate the sum ofUNIQ(substring)
over all non-empty substrings ofS
.If there are two or more equal substrings at different positions in
S
, we consider them different.Since the answer can be very large, return the answer modulo
10 ^ 9 + 7
.
Example 1:
Input: "ABC"Output: 10Explanation: All possible substrings are: "A","B","C","AB","BC" and "ABC".Evey substring is composed with only unique letters.Sum of lengths of all substring is 1 + 1 + 1 + 2 + 2 + 3 = 10Example 2:
Input: "ABA"Output: 8Explanation: The same as example 1, except uni("ABA") = 1.
Note:
0 <= S.length <= 10000
.
解题思路:在任何子串中,只有出现一次的字符才对最终的结果起作用。假设输入的S为 XXXAXXXXAXXAXXXXX,X表示其他任意字符,现在我们来计算蓝A对最后的输出贡献了多少,很显然在两个红A之间的子串中,只要是包括蓝A的子串都有蓝A的贡献,如果第一个红A到蓝A之间的字符数量是L,蓝A到第二个红A之间的字符数量是R,那么蓝A的贡献就是 L + R + L*R + 1 ,其中L表示蓝A与左边字符组成的子串数量,R为与右边的,L*R为同时与左右结合,1表示不与任何字符结合。所有只有找出所有字符左右两边相同字符出现的位置,即可计算出最终的答案。
代码如下:
class Solution(object): def uniqueLetterString(self, S): """ :type S: str :rtype: int """ dic = {} for i,v in enumerate(S): dic[v] = dic.setdefault(v,[]) + [i] res = 0 import bisect for i,v in enumerate(S): inx = bisect.bisect_left(dic[v], i) before = i after = len(S) - i - 1 if inx - 1 >= 0: before = i - dic[v][inx - 1] - 1 if inx + 1 < len(dic[v]): after = dic[v][inx + 1] - i - 1 res += (before + after + before * after + 1) return res % (pow(10, 9) + 7)