# Count Unique Characters Of All Substrings Of A Given String Problem

## Description

LeetCode Problem 828.

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:

``````1
2
3
4
5
Input: s = "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:

``````1
2
3
Input: s = "ABA"
Output: 8
Explanation: The same as example 1, except countUniqueChars("ABA") = 1.
``````

Example 3:

``````1
2
Input: s = "LEETCODE"
Output: 92
``````

Constraints:

• 1 <= s.length <= 10^5
• s consists of uppercase English letters only.

## Sample C++ Code

``````1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
// Occurences: at first 0, so we'll use 1-based indexing
int cur, prev;

int uniqueLetterString(string& s) {
int i, n = s.size();
long long total = 0LL;
char ch;

// prev - cur - next trio of indexes of char ch
// in how many substrings ch with position cur will be unique?
// potential starting points are [prev + 1, cur], ending points are[cur, next - 1]
// so each time total += (cur - prev) * (next - cur)
for (i = 1; i <= n; i++) {
ch = s[i - 1] - 'A';
total += (cur[ch] - prev[ch]) * (i - cur[ch]);
prev[ch] = cur[ch];
cur[ch] = i;
}

// Haven't counted last occurences yet, so IMAGINE each letter pushed-back to string s
for (ch = 0; ch < 26; ch++)
total += (cur[ch] - prev[ch]) * (n + 1 - cur[ch]);

}
};
``````