動機

看解答時是跪著的，能理解為什麼有人看到解答就想打錢過去了

Problem

Let's define a function countUniqueChars(s) that returns the number of unique characters on s.

  • For example if s = LEETCODE then L, T, C, O, D are the unique characters since they appear only once in s, therefore countUniqueChars(s) = 5.

Given a string s, return the sum of countUniqueChars(t) where t is a substring of s.

Notice that some substrings can be repeated so in this case you have to count the repeated ones too.

 

Example 1:

Input: s = ABCOutput: 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 = 10

Example 2:

Input: s = ABAOutput: 8Explanation: The same as example 1, except countUniqueChars(ABA) = 1.

Example 3:

Input: s = LEETCODEOutput: 92

 

Constraints:

  • 1 <= s.length <= 105
  • s consists of uppercase English letters only.

Sol

AXXXAXXA => 左邊的A到中間的A有4個洞，另一邊有3的洞，所以可以生12個只包含A的string

超神奇，在大家想著怎麼處理重複的substring時，lee215直接把組合算出來，直接加，dp什麼的不用不用

class Solution:
    def uniqueLetterString(self, s: str) -> int:
        tbl = defaultdict(lambda : [-1,-1])
        ret = 0

        for (j,c) in enumerate(s):
            i,k = tbl[c]
            ret += (k-i)*(j-k)
            tbl[c] = [k,j]
        for (i,k) in tbl.values():
            ret += (len(s)-k)*(k-i)
        return ret