828. Unique Letter String

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`.

On this problem given a string `s` we need to return the sum of `countUniqueChars(t)` where `t` is a substring of `s`. Notice that some substrings can be repeated so on this case you have to count the repeated ones too.

Since the answer can be very large, return the answer modulo `10 ^ 9 + 7`.

Example 1:

``````Input: s = "ABC"
Output: 10
Explanation: All possible substrings are: "A","B","C","AB","BC" and "ABC".
Evey 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:

• `0 <= s.length <= 10^4`
• `s` contain upper-case English letters only.

``````class Solution {
public:
int uniqueLetterString(string S) {
int res = 0, n = S.size(), M = 1e9 + 7;
vector<vector<int>> idx(26, vector<int>(2, -1));
for (int i = 0; i < n; ++i) {
int c = S[i] - 'A';
res = (res + (i - idx[c][1]) * (idx[c][1] - idx[c][0]) % M) % M;
idx[c][0] = idx[c][1];
idx[c][1] = i;
}
for (int c = 0; c < 26; ++c) {
res = (res + (n - idx[c][1]) * (idx[c][1] - idx[c][0]) % M) % M;
}
return res;
}
};
``````

``````class Solution {
public:
int uniqueLetterString(string S) {
int res = 0, n = S.size(), cur = 0, M = 1e9 + 7;
vector<int> first(26), second(26);
for (int i = 0; i < n; ++i) {
int c = S[i] - 'A';
cur = cur + 1 + i - first[c] * 2 + second[c];
res = (res + cur) % M;
second[c] = first[c];
first[c] = i + 1;
}
return res;
}
};
``````

Github 同步地址:

https://github.com/grandyang/leetcode/issues/828

https://leetcode.com/problems/count-unique-characters-of-all-substrings-of-a-given-string/

https://leetcode.com/problems/count-unique-characters-of-all-substrings-of-a-given-string/discuss/158378/Concise-DP-O(n)-solution

https://leetcode.com/problems/count-unique-characters-of-all-substrings-of-a-given-string/discuss/128952/C%2B%2BJavaPython-One-pass-O(N)

https://leetcode.com/problems/count-unique-characters-of-all-substrings-of-a-given-string/discuss/129021/O(N)-Java-Solution-DP-Clear-and-easy-to-Understand

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation