[2262] Total Appeal of A String | Hard | contest 291

🔎 문제설명

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.

이건 예제 보시면 바로 이해됩니다.

Example 1

Input: s = "abbca"
Output: 28

- Substrings of length 1: "a", "b", "b", "c", "a" have an appeal of 1, 1, 1, 1, and 1 respectively. The sum is 5.
- Substrings of length 2: "ab", "bb", "bc", "ca" have an appeal of 2, 1, 2, and 2 respectively. The sum is 7.
- Substrings of length 3: "abb", "bbc", "bca" have an appeal of 2, 2, and 3 respectively. The sum is 7.
- Substrings of length 4: "abbc", "bbca" have an appeal of 3 and 3 respectively. The sum is 6.
- Substrings of length 5: "abbca" has an appeal of 3. The sum is 3.
The total sum is 5 + 7 + 7 + 6 + 3 = 28.

Example 2

Input: s = "code"
Output: 20

- Substrings of length 1: "c", "o", "d", "e" have an appeal of 1, 1, 1, and 1 respectively. The sum is 4.
- Substrings of length 2: "co", "od", "de" have an appeal of 2, 2, and 2 respectively. The sum is 6.
- Substrings of length 3: "cod", "ode" have an appeal of 3 and 3 respectively. The sum is 6.
- Substrings of length 4: "code" has an appeal of 4. The sum is 4.
The total sum is 4 + 6 + 6 + 4 = 20.

제한사항

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

---

🧊 파이썬 코드

풀이코드 참조했습니다.

다른사람 코드

class Solution:
    def appealSum(self, s):
        last = {}
        res = 0
        for i,c in enumerate(s):
            last[c] = i + 1
            res += sum(last.values())
        return res

코드를 보고도 이해가 안돼서 디버깅해봤습니다.

input : "abbca"

1. {'a': 1}
res  1
2. {'a': 1, 'b': 2}
res  4
3. {'a': 1, 'b': 3}
res  8
4. {'a': 1, 'b': 3, 'c': 4}
res  16
5. {'a': 5, 'b': 3, 'c': 4}
res  28

1. a로 만들수 있는 수식
'a' = 1

2. a와 b로 만들수 있는 수식
'a' 'b' 'ab' = 1 + 1 + 2 = 4

3. a, b, b
'a' 'b' 'ab' 'b' 'bb' 'abb' = 1 + 1 + 2 + 1 + 1 + 2 = 8

여기까지만 해봐도 규칙이 보이네요 (이걸 어떻게 알고 풀지..)

전 HARD 난이도에 범접할 레벨은 아닌 것 같습니다.