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 Table String

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 <= 10⁵
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.

1import java.util.Arrays;2 3class Solution {4    public long appealSum(String s) {5        long totalAppeal = 0;6        int n = s.length();7        // lastSeen[char_code] stores the last index where the character appeared.8        int[] lastSeen = new int[26];9        Arrays.fill(lastSeen, -1);10 11        for (int i = 0; i < n; i++) {12            char c = s.charAt(i);13            int charIndex = c - 'a';14            15            int prevIndex = lastSeen[charIndex];16            17            // Number of substrings where s[i] is the first occurrence of this character.18            // A substring s[start..end] must satisfy:19            // prevIndex < start <= i20            // i <= end < n21            // Number of choices for start: i - prevIndex22            // Number of choices for end: n - i23            long contribution = (long)(i - prevIndex) * (n - i);24            25            totalAppeal += contribution;26            27            // Update the last seen index for the current character.28            lastSeen[charIndex] = i;29        }30        31        return totalAppeal;32    }33}

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.

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.

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.

Walkthrough

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.

1import java.util.HashSet;2import java.util.Set;3 4class Solution {5    public long appealSum(String s) {6        long totalAppeal = 0;7        int n = s.length();8        for (int i = 0; i < n; i++) {9            for (int j = i; j < n; j++) {10                String sub = s.substring(i, j + 1);11                Set<Character> distinctChars = new HashSet<>();12                for (char c : sub.toCharArray()) {13                    distinctChars.add(c);14                }15                totalAppeal += distinctChars.size();16            }17        }18        return totalAppeal;19    }20}

Complexity

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.

Trade-offs

Pros

Simple to understand and implement.

Cons

Extremely inefficient and will result in a 'Time Limit Exceeded' error for the given constraints.

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.

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.

Walkthrough

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.

1import java.util.HashSet;2import java.util.Set;3 4class Solution {5    public long appealSum(String s) {6        long totalAppeal = 0;7        int n = s.length();8        for (int i = 0; i < n; i++) {9            Set<Character> distinctChars = new HashSet<>();10            for (int j = i; j < n; j++) {11                distinctChars.add(s.charAt(j));12                totalAppeal += distinctChars.size();13            }14        }15        return totalAppeal;16    }17}

Complexity

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.

Trade-offs

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'.

Solutions

Solution

1class Solution {2public3  long appealSum(String s) {4    long ans = 0;5    long t = 0;6    int[] pos = new int[26];7    Arrays.fill(pos, -1);8    for (int i = 0; i < s.length(); ++i) {9      int c = s.charAt(i) - 'a';10      t += i - pos[c];11      ans += t;12      pos[c] = i;13    }14    return ans;15  }16}

1class Solution {2public:3  long long appealSum(string s) {4    long long ans = 0, t = 0;5    vector<int> pos(26, -1);6    for (int i = 0; i < s.size(); ++i) {7      int c = s[i] - 'a';8      t += i - pos[c];9      ans += t;10      pos[c] = i;11    }12    return ans;13  }14};

1class Solution:2    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

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 problem

Solution

1class Solution {2public3  long appealSum(String s) {4    long ans = 0;5    long t = 0;6    int[] pos = new int[26];7    Arrays.fill(pos, -1);8    for (int i = 0; i < s.length(); ++i) {9      int c = s.charAt(i) - 'a';10      t += i - pos[c];11      ans += t;12      pos[c] = i;13    }14    return ans;15  }16}

1class Solution {2public:3  long long appealSum(string s) {4    long long ans = 0, t = 0;5    vector<int> pos(26, -1);6    for (int i = 0; i < s.size(); ++i) {7      int c = s[i] - 'a';8      t += i - pos[c];9      ans += t;10      pos[c] = i;11    }12    return ans;13  }14};

1class Solution:2    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

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.