LeetCode 828 Count Unique Characters of All Substrings of a Given String

LeetCode

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.

Given a string s, return the sum of countUniqueChars(t) where t is a substring of s.

Notice that some substrings can be repeated so in this case you have to count the repeated ones too.

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: 1 <= s.length <= 10⁵
* s consists of uppercase English letters only.

题目大意：

求所有子串的唯一字符的个数的总和

解题思路：

暴力法是所有子串O(n^2)，统计唯一字符个数O(n), 复杂度为O(n^3). 尝试优化统计那一步，用presum map来详见可以O(1)求得，但内存过大，仍然TLE。
求个个数且是字符串题，考虑用DP。此题还有点似Leetcode 003 Longest Substring Without Repeating Characters。

写几个找规律且从简单开始，也就是没有重复

A: 1
AB: 1                + 2 + 1 = 4, 1是dp[1], 2是以B结尾的2个子串有两个B，最后一个1表示AB串中有一个A  
       B
      AB        
ABC： 4           + 3 + 2 + 1 = 10， 4是dp[2], 2是以C结尾的3个子串有三个C，2个B，1个A. Delta = 6  
        C
       BC
      ABC  
ABCB:10      + 2 + 3 + 0 + 1 = 16, 同理是上一个DP结果和从后往前每个字母在新子串中的唯一数。由于出现重复，B从4个变成2个，前一个B变成0个，其他加法项是不变的。Delta = 6 + 4 - 2 x 2 = 6 公式为Delta = Delta + 当前长度 - (i - 上一个重复元素下标) x 2    
         B
        CB
       BCB
      ABCB  
ABCBA:16 + 4 + 2 + 3 + 0 + 0 = 25 = 16 + delta 验证公式delta = 6 + 5 - 1 x 2 = 9    
          A 
         BA
        CBA
       BCBA
      ABCBA 
ABCBAC:25 + 3 + 4 + 2 + 0 + 0 + 0 = 34 = 25 + delta 验证公式delta = 9 + 6 - (6 - 3) x 2 = 9    
           C 
          AC 
         BAC
        CBAC
       BCBAC
      ABCBAC 
ABCBACA:34 + 2 + 3 + 0 + 2 + 0 + 0 + 0 = 41 = 34 + delta 验证公式delta = 9 + 7 - (7 - 2) x 2 = 6不匹配，新A本来是7个变成2个，而次新A上一轮有4个最多减4个并不能减5个，所以x 2是不对的。      
            A 
           CA 
          ACA 
         BACA
        CBACA
       BCBACA
      ABCBACA

公式为：

Delta = Delta + 当前下标 - 上一个重复元素下标 - (上一个重复元素下标 - 上个重复元素对应的下标)
Res += Delta

公式解释：
delta是每增加一个字符的增量。若每一个字符都不重复，Delta = Delta + 当前长度表示增加了最后一个字符的数量如AB -> ABC
若有重复，就只增加遇到前一个重复前的个数，如ABCB -> ABCBA的4个
若前面重复有2个，就还要减去在算前一个重复时的增量如上图ABCBACA中BACA和CBACA中在BA和CBA时候当时A没有重复，计算了2个

解题步骤：

delta_sum为上一轮的增加的唯一元素个数
delta[i]为下标为i的元素的唯一个数的增量

注意事项：

1. 公式中减去重复个数不能乘以2，因为上一个重复元素的增量可能不够减

Python代码：

def uniqueLetterString(self, s: str) -> int:
	res, delta_sum, delta, char_to_index = 0, 0, [0] * len(s), collections.defaultdict(lambda: -1)
	for i in range(len(s)):
		cur_len = i + 1
		delta[i] = cur_len
		if s[i] in char_to_index:
			delta[i] -= char_to_index[s[i]] + 1
			delta_sum += delta[i] - delta[char_to_index[s[i]]]
			delta[char_to_index[s[i]]] = 0
		else:
			delta_sum += delta[i]
		res += delta_sum
		char_to_index[s[i]] = i
	return res

算法分析：

时间复杂度为O(n)，空间复杂度O(n)

---

两个Map算法II解题思路(推荐)：

公式中上个重复元素对应的加法项也就是上个重复元素与上上个重复元素的距离，所以引入另一个map来记录，避免用delta[i]，算法更加简单。

Python代码：

def uniqueLetterString(self, s: str) -> int:
	last_char_to_index = collections.defaultdict(lambda: -1)
	last_last_char_to_index = collections.defaultdict(lambda: -1)
	res, delta = 0, 0
	for i, c in enumerate(s):
		delta += i - last_char_to_index[c] - (last_char_to_index[c] - last_last_char_to_index[c])
		last_last_char_to_index[c] = last_char_to_index[c]
		last_char_to_index[c] = i
		res += delta
	return res

算法分析：

时间复杂度为O(n)，空间复杂度O(n)