<p>The <b>appeal</b> of a string is the number of <strong>distinct</strong> characters found in the string.</p>

<ul>
	<li>For example, the appeal of <code>&quot;abbca&quot;</code> is <code>3</code> because it has <code>3</code> distinct characters: <code>&#39;a&#39;</code>, <code>&#39;b&#39;</code>, and <code>&#39;c&#39;</code>.</li>
</ul>

<p>Given a string <code>s</code>, return <em>the <strong>total appeal of all of its <strong>substrings</strong>.</strong></em></p>

<p>A <strong>substring</strong> is a contiguous sequence of characters within a string.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;abbca&quot;
<strong>Output:</strong> 28
<strong>Explanation:</strong> The following are the substrings of &quot;abbca&quot;:
- Substrings of length 1: &quot;a&quot;, &quot;b&quot;, &quot;b&quot;, &quot;c&quot;, &quot;a&quot; have an appeal of 1, 1, 1, 1, and 1 respectively. The sum is 5.
- Substrings of length 2: &quot;ab&quot;, &quot;bb&quot;, &quot;bc&quot;, &quot;ca&quot; have an appeal of 2, 1, 2, and 2 respectively. The sum is 7.
- Substrings of length 3: &quot;abb&quot;, &quot;bbc&quot;, &quot;bca&quot; have an appeal of 2, 2, and 3 respectively. The sum is 7.
- Substrings of length 4: &quot;abbc&quot;, &quot;bbca&quot; have an appeal of 3 and 3 respectively. The sum is 6.
- Substrings of length 5: &quot;abbca&quot; has an appeal of 3. The sum is 3.
The total sum is 5 + 7 + 7 + 6 + 3 = 28.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;code&quot;
<strong>Output:</strong> 20
<strong>Explanation:</strong> The following are the substrings of &quot;code&quot;:
- Substrings of length 1: &quot;c&quot;, &quot;o&quot;, &quot;d&quot;, &quot;e&quot; have an appeal of 1, 1, 1, and 1 respectively. The sum is 4.
- Substrings of length 2: &quot;co&quot;, &quot;od&quot;, &quot;de&quot; have an appeal of 2, 2, and 2 respectively. The sum is 6.
- Substrings of length 3: &quot;cod&quot;, &quot;ode&quot; have an appeal of 3 and 3 respectively. The sum is 6.
- Substrings of length 4: &quot;code&quot; has an appeal of 4. The sum is 4.
The total sum is 4 + 6 + 6 + 4 = 20.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= s.length &lt;= 10<sup>5</sup></code></li>
	<li><code>s</code> consists of lowercase English letters.</li>
</ul>

class Solution:
    def appealSum(self, s: str) -> int:
        """Solution 1:"""
        # there are (n choose 2) + n substrings
        # so we could easily do this problem in O(n^2) time
        # however, we should try and take advantage of the fact that the alphabet comprising
        # this substring is only of length 26
        # let us track for each index i the last time a particular letter appeared
        # this allows us to count the number of substrings ending at index i that contain
        # a letter
        # we will count, for each letter, the number of substrings containing that letter,
        # because this tells us the total appeal contributed by that letter
        n = len(s)
        res = 0
        last_appearance = {}
        for i in range(n):
            c = s[i]
            last_appearance[c] = i
            for a in last_appearance:
                # add in the number of substrings ending at i that contain letter a
                # note that we are not adding their appeal. all we are saying is that
                # each of these substrings has appeal of 1 contributed by letter a,
                # and this is what we are counting
                res += last_appearance[a] + 1
        return res

        """Solution 2:"""
        # recent = {}
        # res = 0
        # for i, c in enumerate(s):
        #     # this looks stupid, but it is done to ensure that the values of the dictionary appear
        #     # in sorted order when we iterate over them
        #     # i.e., when we later do "for past_c in recent" then the idx = recent[past_c] appear in
        #     # sorted order
        #     # recall this works because in python3, the iterator over the dictionary respects
        #     # the order in which keys were added
        #     if c in recent:
        #         del recent[c]
        #     recent[c] = i

        #     appeal = len(recent)
        #     past_idx = -1
        #     for past_c in recent:
        #         idx = recent[past_c]
        #         res += appeal * (idx - past_idx)
        #         appeal -= 1
        #         past_idx = idx
        # return res
695