Java C++ 算法leetcode828统计子串中唯一字符乘法原理

Java C++ 算法leetcode828统计子串中唯一字符乘法原理

题目描述

给定一个字符串，你需要统计其中唯一字符的个数。

具体地，你需要统计所有的出现恰好一次的字符的个数。

示例

输入: "ABCDEF"
输出: 6
解释: 
出现一次的字符有 'A', 'B', 'C', 'D', 'E', 'F'，因此唯一字符的个数为 6。

输入: "ABCDEFABCDEF"
输出: 0
解释: 
都出现了两次的字符，因此没有唯一字符。

解题思路

这道题可以看成是对于任意子串求解唯一字符的个数，这个问题可以被下面的定理所解决：

对于任意的 $i\le j$，$\text{count(i,j)} = \text{count(1,j)} - \text{count(1,i-1)}$，其中 $\text{count(i,j)}$ 表示区间 $[i,j]$ 中唯一字符的个数。

证明如下：

• 显然，当 $i=j$ 时，$\text{count(i,j)}=1$，因为这是一个单个字符。

• 当 $i<j$ 时，我们需要考虑将何时出现重复字符：

  • 假设 $\text{count(1,j)} - \text{count(1,i-1)}=k$，表示区间 $[i,j]$ 中唯一字符的个数为 $k$，则代表区间 $[i,j]$ 中有 $j-i+1-k$ 个字符出现至少两次。

  • 我们接下来考虑新加入一个字符 $c$，并判断这个字符是否会让唯一字符的个数改变：

    • 如果 $c$ 之前在区间 $[i,j]$ 中尚未出现过，由于它是唯一字符，所以唯一字符个数加一。
    • 如果 $c$ 之前在区间 $[i,j]$ 中已经出现过了，那么此时该字符和之前的某个字符 $\hat{c}$ 都存在了，所以唯一字符个数就少了一个。

  • 因此，当我们加入新的 $c$ 时，唯一字符个数的变化可以通过判断 $c$ 是否在区间 $[i,j]$ 中出现来进行决策：

    • 如果 $c$ 在区间内未出现，那么唯一字符个数加一；
    • 如果 $c$ 在区间内已经出现，那么唯一字符个数减一。

  • 由此可以得到结论：区间 $[i+1,j]$ 中唯一字符个数是区间 $[i,j]$ 的唯一字符个数加零或减一。

因此，我们可以用滑动窗口来维护区间的唯一字符个数，每次增加一位字符，就按照定理来决定是否增加或减少唯一字符的个数即可。

代码示例

Java:

public int uniqueLetterString(String S) {
    if(S == null || S.length() == 0) {
        return 0;
    }
    int n = S.length();
    int[] lastIndex = new int[26];
    int[] contribution = new int[26];
    Arrays.fill(lastIndex, -1);
    long result = 0;
    int mod = 1000000007;
    for(int i = 0; i < n; i++) {
        int index = S.charAt(i) - 'A';
        if(lastIndex[index] == -1) {
            contribution[index] = (i + 1);
        } else {
            contribution[index] = (i - lastIndex[index]);
        }
        lastIndex[index] = i;
        result = (result + contribution[index]) % mod;
    }
    return (int)result;
}

C++:

class Solution {
public:
    int uniqueLetterString(string S) {
        if (S.empty()) {
            return 0;
        }
        int n = S.size();
        vector<int> lastIndex(26, -1), contribution(26, 0);
        long long result = 0;
        const int mod = 1e9 + 7;
        for(int i = 0; i < n; i++) {
            int index = S[i] - 'A';
            if(lastIndex[index] == -1) {
                contribution[index] = (i + 1);
            } else {
                contribution[index] = (i - lastIndex[index]);
            }
            lastIndex[index] = i;
            result = (result + contribution[index]) % mod;
        }
        return result;
    }
};

总结

这题用了一个很巧妙的思想。了解这个变换可以帮助我们快速求解子串的相关问题，这里推荐一下书籍：《算法竞赛进阶指南》。