Total Appeal of a String

Sum, over every substring, the count of distinct characters — contribution of each position.

Hard
Time O(N) Space O(1)
LeetCode
3 min read
hash-map math contribution

Problem#

The “appeal” of a string is the count of distinct characters in it. Given s, return the sum of the appeal over all of its non-empty substrings.

Examples#

  • s = "abbca"28.
  • s = "code"20.

Constraints#

  • 1 <= s.length <= 10^5.

Hints#

Hint
Compute each character’s contribution: how many substrings include it as a new distinct character.

Approach#

Each character at position i contributes 1 to every substring that contains it but does not contain another copy of the same letter to its left. If last[c] was the previous occurrence of c (or -1 if none), then position i adds (i - last[c]) to the running sum at this step. Use a per-letter last[26] array.

Solution#

Total Appeal of a String
class Solution {
public:
long long appealSum(string s) {
long long ans = 0, cur = 0;
vector<int> last(26, -1);
for (int i = 0; i < (int)s.size(); ++i) {
int c = s[i] - 'a';
cur += i - last[c];
ans += cur;
last[c] = i;
}
return ans;
}
};

Editorial#

cur is the sum of distinct counts of all substrings ending at i. When s[i] is processed, it adds 1 to every substring ending at i that starts after the previous occurrence of s[i] — that’s i - last[c] substrings. We accumulate this delta into cur, then accumulate cur into ans. The whole thing runs in one pass.

Complexity#

  • Time: O(N).
  • Space: O(1).

Concept revision#

Search ESC

Keyboard shortcuts

Shortcuts are disabled while typing in inputs.