<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:            
        # Penalty:
        # b: bb, abb, bbc, abbc, bbca, abbca lose 6
        # a: abbca, lose 1
        
        # What is the max if totally unique?
        # 5*1 + 4*2 + 3*3 + 4*2 + 1*5 = 5 + 8 + 9 + 8 + 5 = 10 + 16 + 9 = 10 + 25 = 35
        # But from that, we take away 7
        # Leaves you with 28
        
        # Now lets try:
        # abbba
        
        # first b penalty: bb, abb, bbb, abbb, bbba, abbba (6)
        # second b pair penalty: bb, bbb, bba, abbb, bbba, abbba, (6)
        # a penalty: abbba (1)
        # Theoretical score is 5*1 + 4*2 + 3*3 + 2*4 + 5*1 = 35
        # 13 in penalties
        
        # a, b, b, b, a (5)
        # ab, bb, bb, ba (6)     (bb) (bb)
        # abb, bbb, bba (5)      (abb) (bbb)x2 (bba) 
        # abbb, bbba (4)         (abbb)x2 (bbba)x2
        # abbba (2)              (abbba)x3
        # total score is 5+6+5+4+2 = 22
        
        # For each number, find the number of spaces between the next instance of that number
        # Once we find it, we need to penalize by counting how many substrings include both of these numbers
        # Let d be the distance between two guys:
        # if d=1, and l=5. Then its the number of substrings of something of len(4) = 4+3+2+1
        
        # aXbc
        # how many substrings contain X? X, aX, Xb, aXb, Xbc, aXbc
        # aXbcd: X, aX, Xb, aXb, Xbc, aXbc, Xbcd, aXbcd (1+2+2+2+1)
        
        last_found_index = {}
        total_len = len(s)
        penalty = 0
        
        for i in range(total_len):
            val = s[i]
            if val in last_found_index:
                print(val)
                distance = i - last_found_index[val]
                
                # Total number of substrings
                n = (total_len - distance)
                total_substrings = (n * (n+1) // 2)
                
                # Substrings not including your target
                distance_left = last_found_index[val]
                distance_right = total_len - i - 1
                
                left_gain = (distance_left * (distance_left+1) // 2)
                right_gain = (distance_right * (distance_right+1) // 2)
                
                penalty += total_substrings - left_gain - right_gain
            
            last_found_index[val] = i
            
        
        theoretical_best = 0
        for i in range(1, total_len+1):
            theoretical_best += i * (total_len - i + 1)
        
        return theoretical_best - penalty
        
        
        
        
        
        
        
449