子串分值

对于字符串ababc有以下子串

子串

由题意可知同一字符只能为数组提供一个分值，根据子串图变可知字符串中每一个字符所作用范围。

由此可得时间复杂度为O(n^2)的算法。

此时可以用空间换时间

把每个字符最后出现的位置记录下来，使得不用再遍历字符的左边，此时得到时间复杂度为O(n)的算法。