LeetCode-828. Unique Letter String

LeetCode-828. Unique Letter String

A character is unique in string ​​S​​ if it occurs exactly once in it.

For example, in string ​​S = "LETTER"​​​, the only unique characters are ​​"L"​​​ and ​​"R"​​.

Let's define ​​UNIQ(S)​​​ as the number of unique characters in string ​​S​​.

For example, ​​UNIQ("LETTER") =  2​​.

Given a string ​​S​​​ with only uppercases, calculate the sum of ​​UNIQ(substring)​​​ over all non-empty substrings of ​​S​​.

If there are two or more equal substrings at different positions in ​​S​​, we consider them different.

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

Example 1:

Input: "ABC"Output: 10Explanation: 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: "ABA"Output: 8Explanation: The same as example 1, except uni("ABA") = 1.

Note: ​​0 <= S.length <= 10000​​.

题解：

last记录每个字母最后出现的位置，num记录每个字母对于结果贡献的长度，cur记录当前位置为结果的子串所有不重复字符个数。

​​Solution {public: int uniqueLetterString(string S) { int mod = 10e9 + 7; int n = S.length(); vector last(26, 0); vector num(26, 0); long long cur = 0, res = 0; for (int i = 0; i < n; i++) { int k = S[i] - 'A'; cur = (cur - num[k]); num[k] = (i - last[k] + 1); cur = (cur + num[k]) % mod; last[k] = i + 1; res = (res + cur) % mod; } return res % mod; }};

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。