please explain logically, and give simple js solution

====

Count Unique Characters of All Substrings of a Given String

Anonymous User
27788
May 05, 2018
Editorial
Approach #1: Maintain Answer of Suffix [Accepted]
Intuition

We can think of substrings as two for-loops, for the left and right boundary of the substring. To get a handle on this problem, let's try to answer the question: what is the answer over all substrings that start at index i? Let's call this F(i). If we can compute this faster than linear (brute force), we have an approach.

Now let U be the unique letters function, eg. U("LETTER")=2.

The key idea is we can write U as a sum of disjoint functions over each character. Let U 
"A"
​
 (x) be 1 if "A" occurs exactly once in x, otherwise 0, and so on with every letter. Then U(x)=∑ 
c∈A
​
 U 
c
​
 (x), where A={"A","B",…} is the alphabet.

Algorithm

This means we only need to answer the following question (26 times, one for each character): how many substrings have exactly one "A"? If we knew that S[10] = S[14] = S[20] = "A" (and only those indexes have an "A"), then when i = 8, the answer is 4 (j = 10, 11, 12, 13); when i = 12 the answer is 6 (j = 14, 15, 16, 17, 18, 19), and so on.

In total, F(0)=∑ 
c∈A
​
 index[c][1]−index[c][0], where index[c] are the indices i (in order) where S[i] == c (and padded with S.length if out of bounds). In the above example, index["A"] = [10, 14, 20].

Now, we want the final answer of ∑ 
i≥0
​
 F(i). There is a two pointer approach: how does F(1) differ from F(0)? If for example S[0] == "B", then most of the sum remains unchanged (specifically, ∑ 
c∈A,c

="B"
​
 index[c][1]−index[c][0]), and only the c="B" part changes, from index["B"][1]−index["B"][0] to index["B"][2]−index["B"][1].

We can manage this in general by keeping track of peek[c], which tells us the correct index i = peek[c] such that our current contribution by character c of F(i) is index[c][peek[c] + 1] - index[c][peek[c]].


Complexity Analysis

Time Complexity: O(N), where N is the length of S.

Space Complexity: O(N).

Approach #2: Split by Character [Accepted]
Intuition

As in Approach #1, we have U(x)=∑ 
c∈A
​
 U 
c
​
 (x), where A={"A","B",…} is the alphabet, and we only need to answer the following question (26 times, one for each character): how many substrings have exactly one "A"?

Algorithm

Consider how many substrings have a specific "A". For example, let's say S only has three "A"'s, at 'S[10] = S[14] = S[20] = "A"; and we want to know the number of substrings that contain S[14]. The answer is that there are 4 choices for the left boundary of the substring (11, 12, 13, 14), and 6 choices for the right boundary (14, 15, 16, 17, 18, 19). So in total, there are 24 substrings that have S[14] as their unique "A".

Continuing our example, if we wanted to count the number of substrings that have S[10], this would be 10 * 4 - note that when there is no more "A" characters to the left of S[10], we have to count up to the left edge of the string.

We can add up all these possibilities to get our final answer.


Complexity Analysis

Time Complexity: O(N), where N is the length of S.

Space Complexity: O(N). We could reduce this to O(A) if we do not store all the indices, but compute the answer on the fly.

========

828. Count Unique Characters of All Substrings of a Given String
Hard
Topics
Companies
Let's define a function countUniqueChars(s) that returns the number of unique characters in s.

For example, calling countUniqueChars(s) 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. 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: 10
Explanation: All possible substrings are: "A","B","C","AB","BC" and "ABC".
Every 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 = "ABA"
Output: 8
Explanation: The same as example 1, except countUniqueChars("ABA") = 1.
Example 3:

Input: s = "LEETCODE"
Output: 92
 

Constraints:

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