Total Appeal of a String
Sum, over every substring, the count of distinct characters — contribution of each position.
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
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#
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; }};func appealSum(s string) int64 { var ans, cur int64 last := [26]int{} for i := range last { last[i] = -1 } for i := 0; i < len(s); i++ { c := int(s[i] - 'a') cur += int64(i - last[c]) ans += cur last[c] = i } return ans}class Solution: def appealSum(self, s: str) -> int: ans = 0 cur = 0 last = [-1] * 26 for i, ch in enumerate(s): c = ord(ch) - ord('a') cur += i - last[c] ans += cur last[c] = i return ansvar appealSum = function(s) { let ans = 0, cur = 0; const last = new Array(26).fill(-1); for (let i = 0; i < s.length; i++) { const c = s.charCodeAt(i) - 97; cur += i - last[c]; ans += cur; last[c] = i; } return ans;};class Solution { public long appealSum(String s) { long ans = 0, cur = 0; int[] last = new int[26]; Arrays.fill(last, -1); for (int i = 0; i < s.length(); i++) { int c = s.charAt(i) - 'a'; cur += i - last[c]; ans += cur; last[c] = i; } return ans; }}function appealSum(s: string): number { let ans: number = 0, cur: number = 0; const last: number[] = new Array(26).fill(-1); for (let i = 0; i < s.length; i++) { const c: number = s.charCodeAt(i) - 97; 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#
Related#