## 题目描述：

LeetCode 828. Unique Letter String

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 string `S`.

For example, `UNIQ("LETTER") =  2`.

Given a string S, calculate the sum of `UNIQ(substring)` over all non-empty substrings of `S`.

If there are two or more equal substrings at different positions in `S`, we consider them different.

Since the answer can be very large, retrun the answer modulo `10 ^ 9 + 7`.

Example 1:

```Input: "ABC"
Output: 10
Explanation: 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 = 10```

Example 2:

```Input: "ABA"
Output: 8
Explanation: The same as example 1, except uni("ABA") = 1.
```

Note: `0 <= S.length <= 10000`.

## 解题思路：

```分别统计每个字母出现的下标

## Python代码：

``````class Solution(object):
def uniqueLetterString(self, S):
"""
:type S: str
:rtype: int
"""
letterIdx = collections.defaultdict(list)
for i, c in enumerate(S): letterIdx[c].append(i)
ans = 0
for letter, idx in letterIdx.items():
idx = [-1] + idx + [len(S)]
for x in range(1, len(idx) - 1):
ans += (idx[x] - idx[x - 1]) * (idx[x + 1] - idx[x])
return ans
``````

## Python代码：

``````class Solution(object):
def uniqueLetterString(self, S):
"""
:type S: str
:rtype: int
"""
q = [(set([c]), set([c]), i) for i, c in enumerate(S)]
ans = len(S)
while q:
q0 = []
for c, p, i in q:
if i + 1 == len(S):
continue
if S[i + 1] not in c and S[i + 1] not in p:
elif S[i + 1] in c:
c.remove(S[i + 1])
q0.append((c, p, i + 1))
ans += len(q0[-1][0])
q = q0
return ans
``````

Pingbacks已关闭。