[LeetCode] 828. Unique Letter String

[grandyang]

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.

这道题给了我们一个字符串S，要统计其所有的子串中不同字符的个数之和，这里的子串是允许重复的，而且说结果需要对一个超大数取余，这暗示了返回值可能会很大，这样的话对于纯暴力的解法，比如遍历所有可能的子串并统计不同字符的个数的这种解法肯定是不行的。这道题还真是一点没有辱没其 Hard 标签，确实是一道很有难度的题，不太容易想出正确解法。还好有 李哥 lee215 的帖子，一个帖子的点赞数超过了整个第一页所有其他帖子的点赞数之和，简直是刷题界的 Faker，你李哥永远是你李哥。这里就按照李哥的帖子来讲解吧，首先来看一个字符串 CACACCAC，若想让第二个A成为子串中的唯一，那么必须要知道其前后两个相邻的A的位置，比如 CA(CACC)AC，括号中的子串 CACC 中A就是唯一的存在，同样，对于 CAC(AC)CAC，括号中的子串 AC 中A也是唯一的存在。这样就可以观察出来，只要左括号的位置在第一个A和第二个A之间（共有2个位置），右括号在第二个A和第三个A之间（共有3个位置），这样第二个A在6个子串中成为那个唯一的存在。换个角度来说，只有6个子串可以让第二个A作为单独的存在从而在结果中贡献。这是个很关键的转换思路，与其关注每个子串中的单独字符个数，不如换个角度，对于每个字符，统计其可以在多少个子串中成为单独的存在，同样可以得到正确的结果。这样的话，每个字母出现的位置就很重要了，由于上面的分析说了，只要知道三个位置，就可以求出中间的字母的贡献值，为了节省空间，只保留每个字母最近两次的出现位置，这样加上当前位置i，就可以知道前一个字母的贡献值了。这里使用一个长度为 26x2 的二维数组 idx，因为题目中限定了只有26个大写字母。这里只保留每个字母的前两个出现位置，均初始化为 -1。然后遍历S中每个字母，对于每个字符减去A，就是其对应位置，此时将前一个字母的贡献值累加到结果 res 中，假如当前字母是首次出现，也不用担心，前两个字母的出现位置都是 -1，相减后为0，所以累加值还是0。然后再更新 idx 数组的值。由于每次都是计算该字母前一个位置的贡献值，所以最后还需要一个 for 循环去计算每个字母最后出现位置的贡献值，此时由于身后没有该字母了，就用位置N来代替即可，参见代码如下：

解法一：

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

我们也可以换一种解法，使得其更加简洁一些，思路稍微有些不同，这里参考了 大神 meng789987 的帖子。使用的是动态规划 Dynmaic Programming 的思想，用一个一维数组 dp，其中 dp[i] 表示以 S[i] 为结尾的所有子串中的单独字母个数之和，这样只要把 [0, n-1] 范围内所有的 dp[i] 累加起来就是最终的结果了。更新 dp[i] 的方法关键也是要看重复的位置，比如当前是 AB 的话，此时 dp[1]=3，因为以B结尾的子串是 B 和 AB，共有3个单独字母。若此时再后面加上个C的话，由于没有重复出现，则以C结尾的子串 C，BC，ABC 共有6个单独字母，即 dp[2]=6，怎么由 dp[1] 得到呢？首先新加的字母本身就是子串，所以一定是可以贡献1的，然后由于之前都没有C出现，则之前的每个子串中C都可以贡献1，而原本的A和B的贡献值也将保留，所以总共就是 dp[2] = 1+dp[1]+2 = 6。但若新加的字母是A的话，就比较 tricky 了，首先A本身也是子串，有稳定的贡献1，由于之前已经有A的出现了，所以只要知道了之前A的位置，那么中间部分是没有A的，即子串 B 中没有A，A可以贡献1，但是对于之前的有A的子串，比如 AB，此时新加的A不但不能贡献，反而还会伤害之前A的贡献值，即变成 ABA 了后，不但第二个A不能贡献，连第一个A之前的贡献值也要减去，此时 dp[2] = 1+dp[1]+(2-1)-(1-0) = 4。其中2是当前A的位置，1是前一个A的位置加1，0是再前一个A的位置加1。讲到这里应该就比较清楚了吧，这里还是要知道每个字符的前两次出现的位置，这里用两个数组 first 和 second，不过需要注意的是，这里保存的是位置加1。又因为每个 dp 值只跟其前一个 dp 值有关，所以为了节省空间，并不需要一个 dp 数组，而是只用一个变量 cur 进行累加即可，记得每次循环都要把 cur 存入结果 res 中。那么每次 cur 的更新方法就是前一个 cur 值加上1，再加上当前字母产生的贡献值，减去当前字母抵消的贡献值，参见代码如下：

解法二：

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 同步地址:

#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

LeetCode All in One 题目讲解汇总(持续更新中...)