526互联

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

发布时间 2023-07-27 10:40:56作者: zwyyy456

Description

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

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. The test cases are generated such that the answer fits in a 32-bit integer.

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

 

Example 1:

Input: s = "ABC"
Output: 10
Explanation: All possible substrings are:
"A","B","C","AB","BC" and "ABC".
Every substring is composed with only unique letters.
Sum of lengths of all substring is 1 + 1 + 1 + 2 + 2 + 3 = 10

Example 2:

Input: s = "ABA"
Output: 8
Explanation: The same as example 1, except
countUniqueChars("ABA") = 1.

Example 3:

Input: s = "LEETCODE"
Output: 92

 

Constraints:

  • 1 <= s.length <= 105
  • s consists of uppercase English letters only.

Solution

DP

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

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

Code

DP

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

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;
    }
};