【leetcode】828. Unique Letter String

题目如下：

解题思路：在任何子串中，只有出现一次的字符才对最终的结果起作用。假设输入的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)