2262. Total Appeal of A String

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.

c++

class Solution {
public:
    long long appealSum(string s) {
        long long n = s.length(), res = 0, sum = 0;
        char prv = '#';
        unordered_map<char, queue<long long>> mq;
        for(long long i = 0; i < n; i++) {
            mq[s[i]].push(i);
        }
        for(long long i = 0; i < n; i++) {
            if(prv != s[i]) {
                sum = 0;
                prv = s[i];
                priority_queue<long long, vector<long long>, greater<long long>> pq;
                for(auto& [ch, q]: mq) {
                    if(ch == s[i]) continue;
                    pq.push(q.front());
                }
                long long cnt = 1, last = i;
                while(!pq.empty()) {
                    auto pos = pq.top(); pq.pop();
                    sum += (pos - last) * cnt;
                    cnt++;
                    last = pos;
                }
                sum += (n - last) * cnt;
            } else sum--;
            res += sum;
            mq[s[i]].pop();
            if(mq[s[i]].empty())
                mq.erase(s[i]);
        }
        return res;
    }
};