Scale Engineer

Total Appeal of A String

Hard
#2060Time: 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.
Patterns
Dynamic Programming
Data structures
Hash TableString

Prompt

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

3 approaches with complexity analysis and trade-offs.

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.

Walkthrough

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

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.

Trade-offs

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.

Solutions

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 walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem