Total Appeal of A String

Published: Sep 14, 2022

Hard Hash Table String Dynamic Programming

Problem Description

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.

Constraints:

• `1 <= s.length <= 10**5`
• `s` consists of lowercase English letters

https://leetcode.com/problems/total-appeal-of-a-string/

Examples

``````Example 1:
Input: s = "abbca"
Output: 28
``````
``````Example 2:
Input: s = "code"
Output: 20
``````

Solution

``````class TotalAppealOfAString:
def appealSum(self, s: str) -> int:
count, cur, prev = 0, 0, collections.defaultdict(lambda: -1)
for idx, c in enumerate(s):
cur += idx - prev[c]
prev[c] = idx
count += cur
return count
``````

Complexities

• Time: `O(n)`
• Space: `O(1)` – at most 26, constant