<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 <algorithm>
#include <cctype>
#include <fstream>
#include <ios>
#include <iostream>
#include <istream>
#include <iterator>
#include <map>
#include <memory>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#include <cstring>
#include <locale>
using namespace std;

int countStringWithLetter(string s, char target)
{
    vector<int> pos;
    pos.push_back(-1);
    for (int i = 0; i < s.size(); i++)
    {
        if (s[i] == target)
        {
            pos.push_back(i);
        }
    }
    pos.push_back(s.size());

    // cout << target << endl;
    // for (int p : pos)
    // {
    //     cout << p << " ";
    // }
    // cout << endl;

    // long long result = ((long long)s.size()) * (s.size() + 1) / 2;
    int result = 0;
    for (int i = 1; i < pos.size() - 1; i++)
    {
        int count1 = pos[i] - pos[i - 1] - 1;
        result += count1;

        int count2 = pos[i + 1] - pos[i] - 1;
        result += count2;

        int count3 = count1 * count2;
        result += count3;
        // cout << i << " " << result << endl;
    }
    result += pos.size();
    result -= 2;

    // cout << result << endl;
    // cout << "******" << endl;

    return (int)result;
}

class Solution
{
public:
    int uniqueLetterString(string s)
    {
        bool letters[26];
        memset(letters, 0, sizeof(letters));
        for (char ch : s)
        {
            letters[ch - 'A'] = 1;
        }

        int result = 0;
        for (int i = 0; i < 26; i++)
        {
            if (letters[i])
            {
                result += countStringWithLetter(s, 'A' + i);
            }
        }

        return result;
    }
};
45108