Total Appeal of A String

Hard
1258.

Total Appeal of A String

Total Appeal of A String is a hard coding problem on strings, hash table and dynamic programming, asked in Amazon and Google interviews.

The appeal of a string is the number of distinct characters it contains — the appeal of "kaika" is 3 (k, a, i).

Given s, return the sum of the appeals of all of its substrings. A substring is a contiguous, non-empty run of characters; substrings at different positions are counted separately even when they are equal.

CodeKairo bound: s is at most 10,000 characters here, so the answer always fits in a 32-bit integer.

Example 1

Input
s = "code"
Output
20
Explanation
All letters differ, so every substring's appeal is its length: 4·1 + 3·2 + 2·3 + 1·4.

Example 2

Input
s = "aaa"
Output
6
Explanation
Each of the six substrings has appeal 1.

Example 3

Input
s = "kaika"
Output
31

Constraints

  • 1 <= s.length <= 10^4
  • s consists of lowercase English letters
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @return {number}
 */
var appealSum = function(s) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Total Appeal of A String — Solution in Python, Java & C++

Total Appeal of A String solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.

Total Appeal of A String is a hard coding problem on strings, hash table and dynamic programming, asked in Amazon and Google interviews.

Problem statement

The appeal of a string is the number of distinct characters it contains — the appeal of "kaika" is 3 (k, a, i).

Given s, return the sum of the appeals of all of its substrings. A substring is a contiguous, non-empty run of characters; substrings at different positions are counted separately even when they are equal.

CodeKairo bound: s is at most 10,000 characters here, so the answer always fits in a 32-bit integer.

Example 1

Input: s = "code"
Output: 20
Explanation: All letters differ, so every substring's appeal is its length: 4·1 + 3·2 + 2·3 + 1·4.

Example 2

Input: s = "aaa"
Output: 6
Explanation: Each of the six substrings has appeal 1.

Example 3

Input: s = "kaika"
Output: 31

Constraints

  • 1 <= s.length <= 10^4
  • s consists of lowercase English letters

Hints for Total Appeal of A String

  1. Hint 1

    Flip the sum around: instead of counting distinct letters per substring, count for each position how many substrings it is the one that "introduces" its letter.

  2. Hint 2

    Say a character contributes to a substring when it is the first occurrence of its letter inside that substring.

  3. Hint 3

    For s[i] with the previous occurrence of the same letter at prev (or -1), the substring must start in (prev, i] and may end anywhere in [i, n): that is (i - prev) · (n - i) substrings.

How to solve Total Appeal of A String

Credit each distinct letter of a substring to its leftmost occurrence inside that substring. Then position i is credited by exactly the substrings that start after the previous copy of s[i] and end at or after i.

Approach

  1. Keep last[c], the most recent index of letter c, initialised to -1.
  2. For each i with letter c: add (i - last[c]) · (n - i) to the total.
  3. Set last[c] = i and continue. Return the total.

Why it works

In any substring, each distinct letter has exactly one leftmost occurrence, so summing "is the leftmost occurrence of its letter" over all (position, substring) pairs gives the total appeal. s[i] is the leftmost c in s[l..r] exactly when prev < l <= i <= r, which is (i - prev) choices of l times (n - i) choices of r.

Complexity

  • Time — O(n)
  • Space — O(1) — 26 counters

Pitfalls

  • Enumerating substrings is O(n^2) at best — fine as a check, too slow for long strings.
  • Crediting both the first and the last occurrence double counts letters that repeat.
  • On the original problem (n up to 10^5) the answer needs 64 bits; it fits here only because of the tighter bound.

Reference solution

Python

def appealSum(s: str) -> int:
    last = [-1] * 26
    n = len(s)
    total = 0
    for i, ch in enumerate(s):
        c = ord(ch) - 97
        total += (i - last[c]) * (n - i)
        last[c] = i
    return total

Java

public static int appealSum(String s) {
    int[] last = new int[26];
    Arrays.fill(last, -1);
    int n = s.length();
    long total = 0;
    for (int i = 0; i < n; i++) {
        int c = s.charAt(i) - 'a';
        total += (long) (i - last[c]) * (n - i);
        last[c] = i;
    }
    return (int) total;
}

C++

int appealSum(string s) {
    vector<int> last(26, -1);
    int n = s.size();
    long long total = 0;
    for (int i = 0; i < n; i++) {
        int c = s[i] - 'a';
        total += (long long)(i - last[c]) * (n - i);
        last[c] = i;
    }
    return (int)total;
}

JavaScript

var appealSum = function(s) {
    var last = new Array(26).fill(-1);
    var n = s.length, total = 0;
    for (var i = 0; i < n; i++) {
        var c = s.charCodeAt(i) - 97;
        total += (i - last[c]) * (n - i);
        last[c] = i;
    }
    return total;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Hashing: Hash Maps and Hash Sets