Add Distinct-Letter Counts across Every Substring
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Other
### Problem
The appeal of a string is the number of distinct letters it contains. Given a lowercase string `s`, return the total appeal of all its nonempty contiguous substrings. Substrings at different index intervals count separately, even when their text is identical.
```cpp
class Solution {
public:
long long appealSum(string s);
};
```
### Examples
**Example 1:**
```text
Input: s = "aba"
Output: 9
Explanation: The three single-character intervals contribute 3, the two length-two intervals contribute 4, and the whole string contributes 2.
```
**Example 2:**
```text
Input: s = "zzzz"
Output: 10
Explanation: All ten nonempty index intervals contain exactly one distinct letter.
```
### Constraints
- `1 <= s.length <= 100000`.
- s contains lowercase English letters.
### Clarifying Questions
- Do equal substring spellings at different positions count separately? Yes.
- Does the empty substring contribute? No.
- Can the total exceed a 32-bit integer? Yes; use the return type in the signature.
```hint Check the boundary
Check how repeated letters affect the appeal of a single substring, and distinguish substring positions from distinct substring text.
```
Overview: Sum the number of distinct letters over every nonempty substring. Count repeated substring spellings at different positions separately and return a 64-bit total.
