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

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

• For example, calling countUniqueChars(s) 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.

class Solution {
public:
    int uniqueLetterString(string s) {
        int dp[26][2], n = s.length(), res = 0;
        
        memset(dp,-1,sizeof(dp));
        
        for(int i = 0; i < n; i++) {
            int index = s[i] - 'A';
            res += (i - dp[index][1]) * (dp[index][1] - dp[index][0]);
            dp[index][0] = dp[index][1];
            dp[index][1] = i;
        }
        
        for(int i = 0; i < 26; i++) {
            res += (n - dp[i][1]) * (dp[i][1] - dp[i][0]);
        }
        return res;
    }
};