Total Appeal of A String

HARD

Description

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 <= 10⁵
s consists of lowercase English letters.

Approaches

Checkout 3 different approaches to solve Total Appeal of A String. Click on different approaches to view the approach and algorithm in detail.

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.

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.

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.

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;
    }
}

Complexity Analysis

Time Complexity: O(n). We perform a single pass through the string of length `n`. All operations inside the loop are constant time.Space Complexity: O(1). We use an auxiliary array `lastSeen` of size 26, which is constant as the alphabet size is fixed.

Pros and Cons

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.

Code Solutions

Checking out 3 solutions in different languages for Total Appeal of A String. Click on different languages to view the code.

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;
  }
}

Video Solution

Watch the video walkthrough for Total Appeal of A String

Patterns:

Dynamic Programming

Data Structures:

Hash TableString