Leetcode 2262. Total Appeal of A String

[Woodyiiiiiii]

这道题是第291场周赛的最后一题，题目中字符串s的长度最大为10^5级别，显然O(n^2)级别的时间算法度是不允许的，只能尽量优化算法。

尝试O(nlgn)级别的优化可以吗？思考后发现并不可行， 不能用二分之类的方法。那就考虑用O(n)级别的算法，也就是动态规划，寻找每次迭代的关系。

思考后发现，index + 1为结尾的字符串与index结尾的字符串的递进关系是是什么？或者说加入这个字符对index结尾的字符串增加了多少"appeal"？从字符出现位置出发，可以发现，index+1结尾的字符串可以与以该字符最近一次结尾的子字符串(假设为s1)作对比，因为该字符已经出现过一次，换句话说，加入该字符对s1的appeal无影响。故只要对比两者增加的部分。

以字符串"aabab"举例，"aabab"对于"aaba"增加了'b'字符，即增加了"b"、"ab"、"bab"、"abab"、"aabab"这五个子字符串， 我们可以发现对于包含了上一个'b'字符的子字符串，appeal是与"aaba"字符串产生的appeal是相同的，即"abab"中，appeal个数可以看成是"aba"；所以只看s[j+1...i]、s[j+2...i]到s[i-1...i]这些不包括上一个字符的子字符串多的appeal(假设j是最近一次字符出现位置)，增加的appeal数量为i-j+1。

说到底也就是研究规律。得到答案后倒推肯定简单，做题时自己发现规律肯定难。

代码如下：

class Solution {
    public long appealSum(String s) {
        
        long res = 0;
        int[] prev = new int[26];
        long cur = 0;
        
        for (int i = 0; i < s.length(); ++i) {
            cur += i + 1 - prev[s.charAt(i) - 'a'];
            prev[s.charAt(i) - 'a'] = i + 1;
            res += cur;
        }
        
        return res;
        
    }
}

参考中文题解：

• https://leetcode-cn.com/problems/total-appeal-of-a-string/solution/by-endlesscheng-g405/