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.


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


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



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


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