9 变化量分析法：第 2 弹

828. 统计子串中的唯一字符

前言

「力扣题解」系列致力于分享有价值的题目、探讨更优秀的解法。

这是本系列的第 9 篇题解，更多题解关注 Somnia1337@力扣。

上次讲变化量分析法也是子字符串问题，可以回顾一下：

用变化量分析法解决子串问题

本题是该题的进阶版。

题目描述

难度：🔴困难

标签：#哈希表字符串动态规划

我们定义了一个函数 countUniqueChars(s) 来统计字符串 s 中的唯一字符，并返回唯一字符的个数。

例如：s = "LEETCODE"，则其中 "L", "T","C","O","D" 都是唯一字符，因为它们只出现一次，所以 countUniqueChars(s) = 5。

本题将会给你一个字符串 s，我们需要返回 countUniqueChars(t) 的总和，其中 t 是 s 的子字符串。输入用例保证返回值为 32 位整数。

注意，某些子字符串可能是重复的，但你统计时也必须算上这些重复的子字符串（也就是说，你必须统计 s 的所有子字符串中的唯一字符）。

输入: s = "ABC"
输出: 10
解释: 所有可能的子串为: "A","B","C","AB","BC" 和 "ABC"。
     其中，每一个子串都由独特字符构成。
     所以其长度总和为：1 + 1 + 1 + 2 + 2 + 3 = 10

输入: s = "ABA"
输出: 8
解释: 除了 countUniqueChars("ABA") = 1 之外，其余与示例 1 相同。

解题思路

上题中，我们用一个 int[26] 维护每个字母上次出现的位置，对于本题，考虑字符串 “BCADEAFGA”：

对于以最末一个 'A' 结尾的一组子串，讨论其起点：

在绿区（“FGA”，“GA”，“A”）：第 1 次出现 'A'，唯一字符数加 1。
在红区（“DEAFGA”，“EAFGA”，“AFGA”）：第 2 次出现 'A'，唯一字符数减 1。
在白区（“BCADEAFGA”，“CADEAFGA”，“ADEAFGA”），第 2 次以上出现 'A'，之前已经减过 1 了，因此唯一字符数不变。

用两个 int[26]，l1 和 l2，分别维护每个字母上次、上上次出现的位置，更新当前子串组的唯一字符数之和，累加答案。

复杂度

时间复杂度： $O (N)$
空间复杂度： $O (26)$

代码

Java

class Solution {
    public int uniqueLetterString(String s) {
        int cur = 0, ans = 0;
        int[] l1 = new int[26], l2 = new int[26];
        Arrays.fill(l1, -1);
        Arrays.fill(l2, -1);
        for (int i = 0; i < s.length(); i++) {
            int d = s.charAt(i) - 'A';
            cur += i - 2 * l1[d] + l2[d];
            ans += cur;
            l2[d] = l1[d];
            l1[d] = i;
        }
        return ans;
    }
}

Python

为了方便，Python 使用了字典而非数组。

class Solution:
    def uniqueLetterString(self, s: str) -> int:
        ans = cur = 0
        l1, l2 = {}, {}
        for i, c in enumerate(s):
            cur += i - 2 * l1.get(c, -1) + l2.get(c, -1)
            ans += cur
            l2[c] = l1.get(c, -1)
            l1[c] = i
        return ans

最后

更多系列「外源推文」&「生活分享」关注公众号：

🥑 EmberNecro

Explorer