Published: Sep 14, 2022

## Introduction

Using hash table, find a repeating character style problems are there. This is the same type. However, this problem asks about all substrings, so how to count the result is not easy. Within non-repeating characters range, we should count substrings.

## Problem Description

Let’s define a function

`countUniqueChars(s)`

that returns the number of unique characters on`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.

Constraints:

`1 <= s.length <= 10**5`

`s`

consists of uppercase English letters only.https://leetcode.com/problems/count-unique-characters-of-all-substrings-of-a-given-string/

## Examples

```
Example 1:
Input: s = "ABC"
Output: 10
```

```
Example 2
Input: s = "ABA"
Output: 8
```

```
Example 3:
Input: s = "LEETCODE"
Output: 92
```

## Analysis

Start from a hash table which will keep tracking each letter’s start and end indices so far. While going over the given string, add up a count based on the current letter’s previous start and end indices.

## Solution

```
class CountUniqueCharactersOfAllSubstringsOfAGivenString:
def uniqueLetterString(self, s: str) -> int:
n = len(s)
memo = {c: (-1, -1) for c in ascii_uppercase}
result = 0
for idx, c in enumerate(s):
i, j = memo[c]
result += (j - i) * (idx - j)
memo[c] = (j, idx)
for c in memo:
i, j = memo[c]
result += (n - j) * (j - i)
return result
```

## Complexities

- Time:
`O(n)`

- Space:
`O(1)`