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.
- Difficulty: Hard
- Topics: Strings, Hash Table, Dynamic Programming
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
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^4s consists of lowercase English letters
Hints for Total Appeal of A String
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.
Hint 2
Say a character contributes to a substring when it is the first occurrence of its letter inside that substring.
Hint 3
For
s[i]with the previous occurrence of the same letter atprev(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
- Keep
last[c], the most recent index of letterc, initialised to-1. - For each
iwith letterc: add(i - last[c]) · (n - i)to the total. - Set
last[c] = iand 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 (
nup 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 totalJava
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