828: Count Unique Characters of All Substrings of a Given String

Problem

Problem ID: 828

Title: Count Unique Characters of All Substrings of a Given String

Difficulty: Hard

Description:

Let’s define a function countUniqueChars(s) that returns the number of unique characters on s.

For example if s = “LEETCODE” then “L”, “T”, “C”, “O”, “D” are the unique characters since they appear only once in s, therefore countUniqueChars(s) = 5. Given a string s, return the sum of countUniqueChars(t) where t is a substring of s.

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

Solution

General Idea

The key idea to solving this problem is identify the number of substrings a character contribute. A character will only contribute to the substring if all other characters in the substring.

Implementation

class Solution {
public:
    unordered_map<char, set<int>> m_c_indexes;
    int uniqueLetterString(string s) {
        for (int i = 0; i < s.size(); i++) {
            m_c_indexes[s[i]].insert(i);
        }
        
        int ret = 0;
        
        for (int i = 0; i < s.size(); i++) {
            char c = s[i];
            auto it = m_c_indexes[c].find(i);
            int left_i = 0;
            int right_i = s.size() -1;
            if (it != m_c_indexes[c].begin()) {
                it--;
                left_i = *it + 1;
                it++;
            }
            it++;
            if (it != m_c_indexes[c].end() ) {
                right_i = *it - 1; 
            }
            it--;
            ret += (i - left_i + 1)*(right_i - i + 1);
        }
        return ret;
    }
};