题目描述：

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.

题目大意：

给定字符串S，求其各子串中包含的不重复字母的个数。

解题思路：

字符统计

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

假设字母letter的下标数组为idx，将-1和len(S)插入idx的头部和尾部

则sum((idx[i] - idx[i - 1]) * (idx[i + 1] - idx[i]))为letter出现的总次数

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

朴素解法（Time Limit Exceeded）

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:
                    c.add(S[i + 1])
                elif S[i + 1] in c:
                    c.remove(S[i + 1])
                    p.add(S[i + 1])
                q0.append((c, p, i + 1))
                ans += len(q0[-1][0])
            q = q0
        return ans

 

本文链接：http://bookshadow.com/weblog/2018/05/06/leetcode-unique-letter-string/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码