<p>Let&#39;s define a function <code>countUniqueChars(s)</code> that returns the number of unique characters in&nbsp;<code>s</code>.</p>

<ul>
	<li>For example, calling <code>countUniqueChars(s)</code> if <code>s = &quot;LEETCODE&quot;</code> then <code>&quot;L&quot;</code>, <code>&quot;T&quot;</code>, <code>&quot;C&quot;</code>, <code>&quot;O&quot;</code>, <code>&quot;D&quot;</code> are the unique characters since they appear only once in <code>s</code>, therefore <code>countUniqueChars(s) = 5</code>.</li>
</ul>

<p>Given a string <code>s</code>, return the sum of <code>countUniqueChars(t)</code> where <code>t</code> is a substring of <code>s</code>. The test cases are generated such that the answer fits in a 32-bit integer.</p>

<p>Notice that some substrings can be repeated so in this case you have to count the repeated ones too.</p>

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

<pre>
<strong>Input:</strong> s = &quot;ABC&quot;
<strong>Output:</strong> 10
<strong>Explanation: </strong>All possible substrings are: &quot;A&quot;,&quot;B&quot;,&quot;C&quot;,&quot;AB&quot;,&quot;BC&quot; and &quot;ABC&quot;.
Every substring is composed with only unique letters.
Sum of lengths of all substring is 1 + 1 + 1 + 2 + 2 + 3 = 10
</pre>

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

<pre>
<strong>Input:</strong> s = &quot;ABA&quot;
<strong>Output:</strong> 8
<strong>Explanation: </strong>The same as example 1, except <code>countUniqueChars</code>(&quot;ABA&quot;) = 1.
</pre>

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

<pre>
<strong>Input:</strong> s = &quot;LEETCODE&quot;
<strong>Output:</strong> 92
</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 uppercase English letters only.</li>
</ul>

#include <iostream>
#include <unordered_map>
#include <deque>
#include <string>

class Solution {
public:
    int uniqueLetterString(std::string s) {
        int str_len = s.length();
        std::unordered_map<char, std::deque<int>> last_occurrence;
        int total_len = 0;
        int increment = 0;

        for (int i = 0; i < str_len; i++) {
            int substring_len = i + 1;
            char current_char = s[i];

            if (last_occurrence.find(current_char) == last_occurrence.end()) {
                // If the character is not in the map, initialize deque
                last_occurrence[current_char] = std::deque<int>(1, i);
                increment += i + 1;
            } else {
                // If the character has been seen once
                if (last_occurrence[current_char].size() == 1) {
                    int distance = last_occurrence[current_char][0] + 1;
                    int penalty = 2 * distance;
                    increment = increment + i + 1 - penalty;
                    // Add current index to the front of the deque
                    last_occurrence[current_char].push_front(i);
                }
                // If the character has been seen twice
                else if (last_occurrence[current_char].size() >= 2) {
                    // std::cout << "char: " << current_char << " " << i << std::endl;
                    int first_distance = last_occurrence[current_char][0] - last_occurrence[current_char][1];
                    int second_distance = last_occurrence[current_char][1] + 1;
                    int penalty = 2 * first_distance + second_distance;
                    increment = increment + i + 1 - penalty;
                    // Add current index to the front of the deque
                    // Enforce the deque size limit to 2
                    // if (last_occurrence[current_char].size() == 2) {
                    //     last_occurrence[current_char].pop_back(); // Remove the oldest element
                    // }
                    last_occurrence[current_char].push_front(i);
                    
                }
            }
            total_len += increment;
        }
        return total_len;
    }
};


22769