Description Link to heading

828. Count Unique Characters of All Substrings of a Given String (Hard)

Solution Link to heading

DP Link to heading

This problem can be easily solved using dynamic programming. Let’s define $dp[i]$ as the sum of countUniqueChar(t) values for substrings $t$ ending at $s[i]$. The next step is to find the recurrence relation:

Suppose the character corresponding to $s[i]$ is $c$. For substrings ending at $s[i-1]$, if the substring does not contain $c$, then the countUniqueChar value for the substring ending at $s[i]$ is equal to the value for the substring ending at $s[i-1]$ (i.e., without $c$) plus $1$. If the substring contains one $c$, then the countUniqueChar value for the substring ending at $s[i]$ is equal to the value for the substring ending at $s[i-1]$ minus $1$. If the substring contains two $c$, then the countUniqueChar values for the substrings ending at $s[i]$ and $s[i-1]$ are equal.

We maintain a vector<pair<int, int>> left_same, where left_same[i].second represents the largest index less than $i$ that contains the same character as $s[i]$ and left_same[i].first$ represents the second largest index. Note that the pair` needs to be initialized as $\lbrace -1, -1\rbrace$.

Contribution method Link to heading

We can also use the contribution method to calculate the number of substrings that include $s[i]$ in their countUniqueChar value.

Code Link to heading

DP Link to heading 

class Solution {
  public:
    int uniqueLetterString(string s) {
        int n = s.size();
        vector<int> arr(26, -1);
        vector<pair<int, int>> left_same(n, {-1, -1});
        for (int i = 0; i < n; ++i) {
            if (arr[s[i] - 'A'] != -1) {
                left_same[i].first = left_same[arr[s[i] - 'A']].second;
                left_same[i].second = arr[s[i] - 'A'];
            }
            arr[s[i] - 'A'] = i;
        }
        vector<int> dp(n);
        dp[0] = 1;
        int sum = 1;
        for (int i = 1; i < n; ++i) {
            dp[i] = dp[i - 1] + i - left_same[i].second - (left_same[i].second - left_same[i].first);
            sum += dp[i];
        }
        return sum;
    }
};

Contribution method Link to heading 

class Solution {
  public:
    int uniqueLetterString(string s) {
        vector<vector<int>> same(26);
        int n = s.size();
        for (int i = 0; i < n; ++i) {
            int idx = s[i] - 'A';
            same[idx].push_back(i);
        }
        int res = 0;
        for (int i = 0; i < 26; ++i) {
            for (int j = 0; j < same[i].size(); ++j) {
                int left = 0, right = 0;
                if (j == 0) {
                    left = same[i][j] + 1;
                } else {
                    left = same[i][j] - same[i][j - 1];
                }
                if (j == same[i].size() - 1) {
                    right = n - same[i][j];
                } else {
                    right = same[i][j + 1] - same[i][j];
                }
                res += left * right;
            }
        }
        return res;
    }
};