Published: Sep 14, 2022
Introduction
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
Examples
Example 1:
Input: s = "abbca"
Output: 28
Example 2:
Input: s = "code"
Output: 20
Analysis
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