题目描述

给定一个长度为n的字符串，求该字符串的所有子串的字符种类数。

暴力方法

遍历所有子串，每次求每个子串的字符种类数，然后求和。
时间复杂度 O ( n 2 ) O(n^2) O(n2)

DP

这个之前是真没想过，直到看到了大佬的思路
大佬博客
举个例子详细解释一下，我们直接说明DP的含义dp[i]表示以第i个字符结尾的所有子串的字符种类的和。
很明显dp[i]是依赖于dp[i-1]的。
我们以字符串s=”ogo“举例。

我们从前往后一次遍历i。
当i==0时：
显然dp[0]=1,此时以s[0]结尾的子串只有"o"，所以dp[0]=1
当i==1时：
以s[1]结尾的子串有"g",“og”，其中"g"是完全新产生的字符串，但"og"可以理解为从"o"转移来的字符串，但这次转移增加了字符种类，所以dp[1]=dp[0]+1+1
我们隐约感觉到dp的转移公式和这次的"og"有关了，我们继续往下看。
当i==2时：
以s[2]结尾的子串有"o",“go”,“ogo”,其中最后一个"o"是新产生的，“go”,"ogo"都是由dp[1]中的子串转移来的，其中"go"的种类增加了1，"ogo"的种类没变，所以dp[2]=dp[1]+1+1+0
此时我们可以尝试总结规律了，“ogo"相对于"og"的种类没变的原因是因为"og"中已经先包含了新增加的字符"o”,因此启发我们去记录新增加的字符上一次最后出现的位置，其实在遍历的过程中我们需要记录所有出现过的字符的位置j，每次新增一个字符时，只会影响到j+1到i-1这个区间内的子串。
总结规律可得递推公式,last_occur为记录每个字符最后出现位置的map，默认返回-1，即代表从没出现过。
dp[i]=dp[i-1]+i-last_occur[s[i]]
代码如下

def passwordStrength(password):total = 0current = 0last_occurrence = {}for i, c in enumerate(password):current += i - last_occurrence.get(c, -1)total += currentlast_occurrence[c] = ireturn total