Leetcode 828：独特字符串（超详细的解法！！！）

news/2024/7/24 5:24:26

如果一个字符在字符串 S 中有且仅有出现一次，那么我们称其为独特字符。

例如，在字符串 S = "LETTER" 中，"L" 和 "R" 可以被称为独特字符。

我们再定义 UNIQ(S) 作为字符串 S 中独特字符的个数。

那么，在 S = "LETTER" 中， UNIQ("LETTER") = 2。

对于给定字符串 S，计算其所有非空子串的独特字符的个数（即 UNIQ(substring)）之和。

如果在 S 的不同位置上出现两个甚至多个相同的子串，那么我们认为这些子串是不同的。

考虑到答案可能会非常大，规定返回格式为：结果 mod 10 ^ 9 + 7。

示例 1:

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

示例 2:

输入: "ABA"
输出: 8
解释: 除了子串 UNIQ('ABA') = 1，其余与示例1相同。

说明: 0 <= S.length <= 10000。

解题思路

首先放弃暴力解法（字符串的长度太长了），也就是枚举所有的子串。可以这样思考

A B C
↑

当字符串遍历到A的时候，此时以A为结尾的所有后缀（只有A）独特字符和为1。当字符串遍历到B的时候，此时以B为结尾的后缀（包含B和AB）独特字符和为1+2=3。此时不难发现一个问题，就是每次遍历到下一个字符的时候，需要利用到之前的计算信息，所以可以使用动态规划来解这个问题。

我们每次需要判断当前的字符在之前后缀中是否出现，如果出现了，表示当前字符重复了，我们就不应该添加。所以现在的问题就是计算重复次数。举个例子

A B C B D B
-----------
      ↑
      B 1
    C B 2
  B C B 1
A B C B 2

B在之前以C结尾的后缀中出现过了，此时以B结尾的独特字符个数应该是6+4-2*2=6，也就是以C结尾的独特字符个数加上此时B的个数，最后减去重复B的个数乘2。继续看下一个位置的B满足什么规律。

A B C B D B
-----------
          ↑
          B 1
        D B 2
      B D B 1
    C B D B 2
  B C B D B 2 
A B C B D B 3

此时B在有些后缀中出现了两次，此时以B结尾的独特字符个数应该是11+6-4*2+2=11。此时的算法和之前稍微不同，以D结尾的独特字符个数加上此时B的个数，最后减去重复B的个数乘2。需要注意的是，此时我们多减了一些，因为在以D为结尾的后缀计算中已经减过一次重复B了，那么此时相当于多减了2（也就是有两个后缀出现了B重复两次的情况）。

好，现在还差最后一个问题没有解决，就是如何计算后缀个数？实际上就是位置i的值。重复B的个数，就是当前B的位置减去前一次B的位置。重复两次B的个数，就是前一次B的位置减去前一次的前一次的B的位置。有点绕口，但是希望你理解我的意思O(∩_∩)O哈哈~

我们定义 $f (i)$ 表示以第i个字符结尾的后缀中独特字符的个数，那么转移方程为：

$f (i) = f (i - 1) + (i + n (i) - 2 * m (i))$

其中 $m (i)$ 表示字符s[i]前一次出现的位置， $n (i)$ 表示字符s[i]前一次的前一次出现位置。例如：

B O A B C D O A B C O A B C
  ↑         ↑       ↑
  n         m       i

最后只要将所有的 $f (i)$ 累加就是最后的结果，代码非常简洁。

class Solution:
    def uniqueLetterString(self, S: str) -> int:
        res, mod, f = 0, 10**9 + 7, 0
        m, n = [0]*26, [0]*26
        for i, v in enumerate(S):
            t = ord(v) - 65
            f = f + 1 + i - 2 * m[t] + n[t]
            res = (res + f) % mod
            n[t], m[t] = m[t], i + 1
        return res