# Total Appeal of A String
**Difficulty:** HARD
[External](https://leetcode.com/problems/total-appeal-of-a-string)
Canonical: https://scaleengineer.com/dsa/problems/total-appeal-of-a-string
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** Hash Table, String
---
## Problem
The **appeal** of a string is the number of **distinct** characters found in the string.

* For example, the appeal of `"abbca"` is `3` because it has `3` distinct characters: `'a'`, `'b'`, and `'c'`.

Given a string `s`, return _the **total appeal of all of its substrings.**_

A **substring** is a contiguous sequence of characters within a string.

**Example 1:**

**Input:** s = "abbca"
**Output:** 28
**Explanation:** The following are the substrings of "abbca":
- Substrings of length 1: "a", "b", "b", "c", "a" have an appeal of 1, 1, 1, 1, and 1 respectively. The sum is 5.
- Substrings of length 2: "ab", "bb", "bc", "ca" have an appeal of 2, 1, 2, and 2 respectively. The sum is 7.
- Substrings of length 3: "abb", "bbc", "bca" have an appeal of 2, 2, and 3 respectively. The sum is 7.
- Substrings of length 4: "abbc", "bbca" have an appeal of 3 and 3 respectively. The sum is 6.
- Substrings of length 5: "abbca" has an appeal of 3. The sum is 3.
The total sum is 5 + 7 + 7 + 6 + 3 = 28.

**Example 2:**

**Input:** s = "code"
**Output:** 20
**Explanation:** The following are the substrings of "code":
- Substrings of length 1: "c", "o", "d", "e" have an appeal of 1, 1, 1, and 1 respectively. The sum is 4.
- Substrings of length 2: "co", "od", "de" have an appeal of 2, 2, and 2 respectively. The sum is 6.
- Substrings of length 3: "cod", "ode" have an appeal of 3 and 3 respectively. The sum is 6.
- Substrings of length 4: "code" has an appeal of 4. The sum is 4.
The total sum is 4 + 6 + 6 + 4 = 20.

**Constraints:**

* `1 <= s.length <= 105`
* `s` consists of lowercase English letters.

# Approaches
## Brute Force Enumeration
This approach iterates through all possible substrings of the input string `s`. For each substring, it calculates its appeal (the number of distinct characters) and adds it to a running total. This is the most straightforward but also the most inefficient way to solve the problem.
**Time:** O(n³). There are O(n²) substrings. For each substring of length `k`, calculating its appeal by iterating and adding to a set takes O(k) time. The sum of lengths of all substrings is O(n³), leading to a cubic time complexity. · **Space:** O(n). In each step, a substring of length up to `n` might be created, taking `O(n)` space. The `HashSet` takes `O(1)` space as the alphabet size is fixed at 26.
**Pros:** Simple to understand and implement.
**Cons:** Extremely inefficient and will result in a 'Time Limit Exceeded' error for the given constraints.
### Explanation
The algorithm works by systematically generating every single contiguous substring. For each substring generated, it determines the number of unique characters within it. This is done by using a data structure like a `HashSet` to store the characters of the substring, and the size of the set gives the appeal. The appeals of all substrings are summed up to get the final result.

```java
import java.util.HashSet;
import java.util.Set;

class Solution {
    public long appealSum(String s) {
        long totalAppeal = 0;
        int n = s.length();
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                String sub = s.substring(i, j + 1);
                Set<Character> distinctChars = new HashSet<>();
                for (char c : sub.toCharArray()) {
                    distinctChars.add(c);
                }
                totalAppeal += distinctChars.size();
            }
        }
        return totalAppeal;
    }
}
```
### Algorithm
- Initialize a variable `totalAppeal` to 0.
- Use two nested loops to generate all substrings. The outer loop `i` from 0 to `n-1` defines the start of the substring, and the inner loop `j` from `i` to `n-1` defines the end.
- For each substring `sub = s.substring(i, j + 1)`, calculate its appeal.
- To calculate the appeal of `sub`, create a `HashSet` of characters, iterate through `sub`, and add each character to the set. The size of the set is the appeal.
- Add the calculated appeal to `totalAppeal`.
- After iterating through all substrings, return `totalAppeal`.

## Optimized Brute Force
This is an improvement over the naive brute-force approach. Instead of recalculating the appeal for each substring from scratch, we can compute it incrementally. When we extend a substring `s[i..j-1]` to `s[i..j]`, we only need to consider the new character `s[j]` and update the count of distinct characters.
**Time:** O(n²). We have two nested loops iterating through the string. The operations inside the inner loop (HashSet add and size) take constant time on average. This is better than O(n³) but still insufficient for n = 10⁵. · **Space:** O(1). The `HashSet` stores at most 26 distinct characters, which is constant space.
**Pros:** More efficient than the naive O(n³) brute-force approach.; Still relatively easy to understand.
**Cons:** Still too slow for the given constraints and will result in 'Time Limit Exceeded'.
### Explanation
For a fixed starting index `i`, we can iterate through all possible ending indices `j` from `i` to `n-1`. As we extend the substring one character at a time, we maintain a `HashSet` of the characters seen so far for the current substring `s[i..j]`. Adding a new character `s[j]` and getting the size of the set is an O(1) operation on average. We sum up these sizes for all substrings.

```java
import java.util.HashSet;
import java.util.Set;

class Solution {
    public long appealSum(String s) {
        long totalAppeal = 0;
        int n = s.length();
        for (int i = 0; i < n; i++) {
            Set<Character> distinctChars = new HashSet<>();
            for (int j = i; j < n; j++) {
                distinctChars.add(s.charAt(j));
                totalAppeal += distinctChars.size();
            }
        }
        return totalAppeal;
    }
}
```
### Algorithm
- Initialize `totalAppeal` to 0.
- Use an outer loop `i` from 0 to `n-1` to fix the starting point of substrings.
- Inside the outer loop, create a `HashSet` to keep track of distinct characters for substrings starting at `i`.
- Use an inner loop `j` from `i` to `n-1` to extend the substring.
- In each step of the inner loop, add the character `s.charAt(j)` to the `HashSet`.
- The size of the `HashSet` at this point is the appeal of the substring `s.substring(i, j + 1)`.
- Add this appeal to `totalAppeal`.
- After the loops complete, return `totalAppeal`.

## Linear Time Solution using Contribution of Characters
Instead of iterating through substrings, we can change our perspective and calculate the total contribution of each character to the final sum. The total appeal is the sum of appeals of all substrings. This can be rephrased as summing, for each character `c` in the alphabet, the number of substrings that contain `c`. A more direct way is to consider the contribution of each character `s[i]` to the total appeal.
**Time:** O(n). We perform a single pass through the string of length `n`. All operations inside the loop are constant time. · **Space:** O(1). We use an auxiliary array `lastSeen` of size 26, which is constant as the alphabet size is fixed.
**Pros:** Highly efficient, optimal solution that passes all test cases within the time limit.
**Cons:** The logic is less intuitive than brute-force approaches and requires a shift in perspective to counting contributions.
### Explanation
The core idea is that a character `s[i]` adds `+1` to the appeal of a substring if it's the *first* occurrence of that character within that substring. For a character `s[i]`, we need to count how many substrings `s[start..end]` contain `s[i]` as their first instance of that character.

Let `prev_idx` be the index of the previous occurrence of the character `s[i]` (or -1 if it's the first time). For `s[i]` to be the first occurrence in `s[start..end]`, we must have `start > prev_idx`. Also, the substring must contain `s[i]`, so `start <= i <= end`.

Combining these conditions:
- The `start` index can be any value from `prev_idx + 1` to `i`. This gives `i - (prev_idx + 1) + 1 = i - prev_idx` choices.
- The `end` index can be any value from `i` to `n-1`. This gives `(n-1) - i + 1 = n - i` choices.

Thus, `s[i]` contributes `(i - prev_idx) * (n - i)` to the total appeal. We can iterate through the string once, calculating and summing these contributions.

```java
import java.util.Arrays;

class Solution {
    public long appealSum(String s) {
        long totalAppeal = 0;
        int n = s.length();
        // lastSeen[char_code] stores the last index where the character appeared.
        int[] lastSeen = new int[26];
        Arrays.fill(lastSeen, -1);

        for (int i = 0; i < n; i++) {
            char c = s.charAt(i);
            int charIndex = c - 'a';
            
            int prevIndex = lastSeen[charIndex];
            
            // Number of substrings where s[i] is the first occurrence of this character.
            // A substring s[start..end] must satisfy:
            // prevIndex < start <= i
            // i <= end < n
            // Number of choices for start: i - prevIndex
            // Number of choices for end: n - i
            long contribution = (long)(i - prevIndex) * (n - i);
            
            totalAppeal += contribution;
            
            // Update the last seen index for the current character.
            lastSeen[charIndex] = i;
        }
        
        return totalAppeal;
    }
}
```
### Algorithm
- Initialize `totalAppeal` to 0.
- Create an array `lastSeen` of size 26 and initialize all its elements to -1. This array will store the last index at which each character was seen.
- Iterate through the string `s` from `i = 0` to `n-1`.
- For the character `c = s.charAt(i)`, find its previous index `prev_idx` from `lastSeen[c - 'a']`.
- Calculate the contribution of `s[i]` as `(i - prev_idx) * (n - i)`.
- Add this contribution to `totalAppeal`.
- Update the last seen index for `c`: `lastSeen[c - 'a'] = i`.
- After the loop, return `totalAppeal`.

# Solutions
### Java

```java
class Solution {
public
  long appealSum(String s) {
    long ans = 0;
    long t = 0;
    int[] pos = new int[26];
    Arrays.fill(pos, -1);
    for (int i = 0; i < s.length(); ++i) {
      int c = s.charAt(i) - 'a';
      t += i - pos[c];
      ans += t;
      pos[c] = i;
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  long long appealSum(string s) {
    long long ans = 0, t = 0;
    vector<int> pos(26, -1);
    for (int i = 0; i < s.size(); ++i) {
      int c = s[i] - 'a';
      t += i - pos[c];
      ans += t;
      pos[c] = i;
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def appealSum(self, s: str) -> int: ans = t = 0 pos = [- 1] * 26 for i, c in enumerate(s): c = ord(c) - ord('a') t += i - pos[c] ans += t pos[c] = i return ans

```