[LeetCode]Unique Letter String

这道题可以转化为求[i, j]范围内substring的unique char的个数。Brute Force的做法是枚举所有i和j，然后统计[i,j]内的unique char。时间复杂度O(n^3)，显然不可行。优化的做法是，我们统计所有在i处结尾的substring的unique char的数量。用另一个指针j从i处从右向左扫，一边统计unique char的数量即可，这样我们在O(n)的时间可以统计出所有以i结尾的substring的unique char的数量。总的时间复杂度为O(n^2)，空间复杂度为O(n)，但是仍然会TLE，代码如下：



我们尝试寻找更效率的方法。因为题目说了输入的字符只有大写字母26种，如果我们改变思路统计每个字符分别在多少个substring中出现了一次，假设我们可以O(n)时间内完成这项工作，那么总的时间复杂度也仍然是O(n)。利用这个思路，我们记录每个字符在string s中出现的位置，假设s长度为10，a出现在[0, 5, 8]三处:

1. 所有只包含0处a的substring都满足条件，有5个, [0, 0-4]
2. 所有只包含5处a的substring都满足条件，有15个，[1-5, 5-7]
3. 所有只包含8处a的substring都满足条件，有6个，[6-8, 8-9]

对于每一种字符我们都统计一遍。时间复杂度，空间复杂度均为O(n)，代码如下：

另一种官方给出的解法，思路是类似的，分别统计每个字符。假设idx(c)为字符c在string s中出现的位置，从小到大排列。我们用f[i]['a']表示在i处开头的substring只包含'a'一次的substring，显然f[i] = f[i]['a'] + f[i]['b'] + ... + f[i]['z']。比如idx('a') = [0, 5, 8]，f[0]['a'] = idx('a')[1] - idx('a')[0] = 5，对应[0, 0-4]。如果我们扫到i = 1，f[i]['a']会变，这时候f[1]['a'] = idx('a')[2] - idx('a')[1] = 3，对应[1, 5-7]。剩下的f[i]['b'] ... f[i]['z']并不会变。所以f[1] = f[0] + f[1]['a'] - f[0]['a']。所以我们从左向右扫，算出每个i对应的f[i]即可，我们可以用一个array arr[26]记录对应每个字符c在idx(c)中此时对应的位置，f[i][c] = idx(c)[arr[c - 'a'] + 1] - idx(c)[arr[c - 'a']]。时间复杂度O(n)，代码如下：