Count Unique Characters of All Substrings of a Given String
Let's define a function countUniqueChars(s) that returns the number of unique characters in s.
- For example, calling
countUniqueChars(s)ifs = "LEETCODE"then"L","T","C","O","D"are the unique characters since they appear only once ins, thereforecountUniqueChars(s) = 5.
Given a string s, return the sum of countUniqueChars(t) where t is a substring of s. The test cases are generated such that the answer fits in a 32-bit integer.
Notice that some substrings can be repeated, so in this case you have to count the repeated ones too.
Example 1
Input
s = "ABC"Output
10All possible substrings are
"A", "B", "C", "AB", "BC", and "ABC"; every substring is composed only of unique letters, so the sum is 1 + 1 + 1 + 2 + 2 + 3 = 10.Example 2
Input
s = "ABA"Output
8The same as example 1, except
countUniqueChars("ABA") = 1.Constraints
- 1 <= s.length <= 10^5
- s consists of uppercase English letters only.