# Count Unique Characters of All Substrings of a Given String
**Difficulty:** HARD
[External](https://leetcode.com/problems/count-unique-characters-of-all-substrings-of-a-given-string)
Canonical: https://scaleengineer.com/dsa/problems/count-unique-characters-of-all-substrings-of-a-given-string
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** Hash Table, String
---
## Problem
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.

# Approaches
## Brute Force Iteration
This approach directly follows the problem statement by iterating through all possible substrings of the input string `s`. For each substring, it calculates the number of unique characters and adds this count to a running total. While straightforward, its performance is poor due to the large number of substrings.
**Time:** O(N^2), where N is the length of the string. We have two nested loops, each potentially running up to N times. The operations inside the inner loop are constant time. · **Space:** O(1), as we only use a fixed-size array (size 26) for the frequency map, which does not depend on the input string's length.
**Pros:** Simple to understand and implement.; Uses constant extra space.
**Cons:** Highly inefficient and will result in a 'Time Limit Exceeded' error for large inputs as specified in the constraints (N up to 10^5).
### Explanation
The algorithm generates every substring by using two nested loops. The outer loop fixes the starting point `i` of the substring, and the inner loop iterates from `i` to the end of the string, defining the endpoint `j`. For each starting point `i`, we can efficiently calculate the unique characters for all substrings starting at `i` by extending the substring one character at a time. We use a frequency array to keep track of character counts for the current substring `s[i...j]`. As we extend the substring to `s[i...j+1]`, we update the frequency of the new character and adjust the unique character count accordingly. This count is then added to our overall sum.

```java
class Solution {
    public int uniqueLetterString(String s) {
        int n = s.length();
        int totalSum = 0;
        for (int i = 0; i < n; i++) {
            int[] freq = new int[26];
            int uniqueCount = 0;
            for (int j = i; j < n; j++) {
                int charIndex = s.charAt(j) - 'A';
                freq[charIndex]++;
                if (freq[charIndex] == 1) {
                    uniqueCount++;
                } else if (freq[charIndex] == 2) {
                    uniqueCount--;
                }
                totalSum += uniqueCount;
            }
        }
        return totalSum;
    }
}
```
### Algorithm
*   Initialize a variable `totalSum` to 0.
*   Use a nested loop to generate all substrings. The outer loop `i` from 0 to `n-1` defines the start of the substring.
*   The inner loop `j` from `i` to `n-1` defines the end of the substring.
*   For each substring `s.substring(i, j + 1)`, we need to count its unique characters.
*   To do this efficiently within the loops, we can maintain a frequency map (an array of size 26) for the substring starting at `i`.
*   As `j` increases, we update the frequency of the new character `s.charAt(j)`.
*   We also maintain a count of unique characters for the current substring `s.substring(i, j + 1)`. If a character's frequency becomes 1, we increment the unique count. If it becomes 2, we decrement it.
*   Add this unique count to `totalSum`.
*   After iterating through all substrings, `totalSum` will hold the final answer.

## Sum of Character Contributions
Instead of iterating over substrings, this approach changes the perspective. It calculates the contribution of each character to the total sum. The contribution of a character `s[i]` is the number of substrings in which `s[i]` appears exactly once. By summing these contributions for every character in the string, we arrive at the final answer.
**Time:** O(N), where N is the length of the string. We iterate through the string once to build the map and then iterate through all the indices once more to calculate the sum. · **Space:** O(N) in the worst case (all characters are unique) to store the indices in the map. The space complexity is proportional to the alphabet size `k` plus `N`, so O(k+N), which simplifies to O(N).
**Pros:** Very efficient with a linear time complexity.; The logic is elegant and based on a combinatorial insight.
**Cons:** Requires extra space proportional to the length of the string to store all indices.
### Explanation
To calculate the contribution for each character `s[i]`, we need to determine how many substrings contain `s[i]` as their only instance of that character. This is determined by the positions of the previous and next identical characters. If `s[i]` is at index `i`, its previous occurrence is at `prev_idx`, and its next is at `next_idx`, then any valid substring must start after `prev_idx` and end before `next_idx`. The number of possible start positions is `i - prev_idx`, and the number of end positions is `next_idx - i`. The total contribution for `s[i]` is the product of these two values. We can first iterate through the string to map each character to a list of its indices. Then, for each character's list of indices, we calculate the contributions and sum them up.

```java
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class Solution {
    public int uniqueLetterString(String s) {
        int n = s.length();
        Map<Character, List<Integer>> indexMap = new HashMap<>();
        for (int i = 0; i < n; i++) {
            char c = s.charAt(i);
            indexMap.computeIfAbsent(c, k -> new ArrayList<>()).add(i);
        }

        int totalSum = 0;
        for (Map.Entry<Character, List<Integer>> entry : indexMap.entrySet()) {
            List<Integer> indices = entry.getValue();
            int prevIdx = -1;
            for (int i = 0; i < indices.size(); i++) {
                int currentIdx = indices.get(i);
                int nextIdx = (i + 1 < indices.size()) ? indices.get(i + 1) : n;
                totalSum += (currentIdx - prevIdx) * (nextIdx - currentIdx);
                prevIdx = currentIdx;
            }
        }
        return totalSum;
    }
}
```
### Algorithm
*   The core idea is that `sum(countUniqueChars(t))` over all substrings `t` is equal to `sum(contribution(c))` over all characters `c` in `s`.
*   The contribution of a character `s[i]` is the number of substrings that contain `s[i]` and no other occurrence of the same character.
*   To find this, for each character `s[i]`, we need to know the index of its previous occurrence (`prev_idx`) and its next occurrence (`next_idx`).
*   A substring containing `s[i]` as a unique character must start at an index `l` such that `prev_idx < l <= i` and end at an index `r` such that `i <= r < next_idx`.
*   The number of choices for the start index `l` is `i - prev_idx`.
*   The number of choices for the end index `r` is `next_idx - i`.
*   The contribution of `s[i]` is `(i - prev_idx) * (next_idx - i)`.
*   First, pre-calculate the indices of all occurrences for each character using a `Map<Character, List<Integer>>`.
*   Iterate through each character `C` in the map's key set.
*   For each `C`, get its list of indices. To handle boundary conditions, conceptually add `-1` at the beginning and `n` (string length) at the end of the list.
*   For each index `curr` in the list, let the previous index be `prev` and the next index be `next`. Calculate the contribution `(curr - prev) * (next - curr)` and add it to `total_sum`.

## Dynamic Programming with Single Pass
This is the most optimized approach, building upon the character contribution idea. It calculates the total sum in a single pass over the string using dynamic programming, which requires only constant extra space (relative to the alphabet size).
**Time:** O(N), as we iterate through the string only once. All operations inside the loop are constant time. · **Space:** O(1), as we only use two fixed-size arrays (size 26) for tracking indices, which is independent of the input string length.
**Pros:** Most efficient solution in both time and space.; Solves the problem in a single pass.
**Cons:** The recurrence relation can be less intuitive to derive compared to the direct contribution counting method.
### Explanation
We define `dp[i]` as the sum of `countUniqueChars` for all substrings ending at index `i`. The final answer is the sum of `dp[i]` for all `i`. We can compute `dp[i]` from `dp[i-1]` in constant time. When considering the character `c = s.charAt(i)`, its addition affects the unique character counts. Let `last_idx` be the index of the previous occurrence of `c`, and `prev_last_idx` be the index before that. The new character `c` contributes `+1` to all substrings ending at `i` that start after `last_idx`. There are `i - last_idx` such substrings. Additionally, the character at `last_idx`, which was previously unique in some substrings ending at `i-1`, is now duplicated. This causes a decrease of `1` for `last_idx - prev_last_idx` substrings. This leads to the recurrence `dp[i] = dp[i-1] + (i - last_idx) - (last_idx - prev_last_idx)`. We can implement this by iterating through the string once, keeping track of the last two indices for each character.

```java
import java.util.Arrays;

class Solution {
    public int uniqueLetterString(String s) {
        int n = s.length();
        // lastIdx[char] stores the last index of 'char'
        int[] lastIdx = new int[26];
        Arrays.fill(lastIdx, -1);
        // prevLastIdx[char] stores the second to last index of 'char'
        int[] prevLastIdx = new int[26];
        Arrays.fill(prevLastIdx, -1);

        int totalSum = 0;
        int currentDp = 0; // Sum of unique chars for substrings ending at current index

        for (int i = 0; i < n; i++) {
            int charIndex = s.charAt(i) - 'A';
            
            // Recurrence: dp[i] = dp[i-1] + (i - last[c]) - (last[c] - prev_last[c])
            currentDp = currentDp + (i - lastIdx[charIndex]) - (lastIdx[charIndex] - prevLastIdx[charIndex]);
            
            totalSum += currentDp;

            // Update indices for the current character
            prevLastIdx[charIndex] = lastIdx[charIndex];
            lastIdx[charIndex] = i;
        }
        return totalSum;
    }
}
```
### Algorithm
*   Let `dp[i]` be the sum of `countUniqueChars` for all substrings ending at index `i`. The final answer is the sum of all `dp[i]`.
*   We can find a recurrence relation for `dp[i]` based on `dp[i-1]`.
*   When we move from index `i-1` to `i` and consider the new character `c = s.charAt(i)`, we are extending all previous substrings ending at `i-1` with `c`, and also forming a new substring of just `c`.
*   Let `prev_idx` be the index of the previous occurrence of `c`, and `second_prev_idx` be the index of the occurrence before that.
*   The new character `c` at index `i` is unique in all substrings `s[k...i]` where `k > prev_idx`. This adds `i - prev_idx` to our sum for substrings ending at `i`.
*   The character `c` at `prev_idx` was previously unique in `prev_idx - second_prev_idx` substrings ending at `i-1`. By adding `c` at index `i`, it's no longer unique, so we subtract this count.
*   The recurrence is: `dp[i] = dp[i-1] + (i - prev_idx) - (prev_idx - second_prev_idx)`.
*   We iterate `i` from 0 to `n-1`, maintaining `dp` and a `total_sum`, while tracking the last two indices of each character.

# Solutions
### Java

```java
class Solution {
public
  int uniqueLetterString(String s) {
    List<Integer>[] d = new List[26];
    Arrays.setAll(d, k->new ArrayList<>());
    for (int i = 0; i < 26; ++i) {
      d[i].add(-1);
    }
    for (int i = 0; i < s.length(); ++i) {
      d[s.charAt(i) - 'A'].add(i);
    }
    int ans = 0;
    for (var v : d) {
      v.add(s.length());
      for (int i = 1; i < v.size() - 1; ++i) {
        ans += (v.get(i) - v.get(i - 1)) * (v.get(i + 1) - v.get(i));
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int uniqueLetterString(string s) {
    vector<vector<int>> d(26, {-1});
    for (int i = 0; i < s.size(); ++i) {
      d[s[i] - 'A'].push_back(i);
    }
    int ans = 0;
    for (auto &v : d) {
      v.push_back(s.size());
      for (int i = 1; i < v.size() - 1; ++i) {
        ans += (v[i] - v[i - 1]) * (v[i + 1] - v[i]);
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def uniqueLetterString(self, s: str) -> int: d = defaultdict(list) for i, c in enumerate(s): d[c]. append(i) ans = 0 for v in d . values(): v = [- 1] + v + [len(s)] for i in range(1, len(v) - 1): ans += (v[i] - v[i - 1]) * (v[i + 1] - v[i]) return ans

```