「LeetCode 828. Unique Letter String」解题报告 | Tashi711的博客
定义unique character为字符串中出现正好一次的字母，定义UNIQ(S)为字符串S中unique character的个数。给定一个只含有大写字母的字符串S，求S的所有非空子串的UNIQ之和，如果两个不同位置的子串相同被认为是不同的子串。结果对10^9+7取模。
样例：1、"ABC"->10；2、"ABA"->8。
解题思路
比较简单的一道题目，考虑每个单独的字母对于最终答案的贡献。如果某个字母a对答案有贡献，那么包含他的子串一定在从这个a往两边延伸到边界或者另一个a之内位置的范围内。那么总共可能的子串有u*v个，其中u、v分别为延伸到边界或者另一个a之内位置的长度。对每个'A'到'Z'的字母a，找到每个a的位置，计算往外延伸的长度，乘起来累加到答案即可
Read full article from 「LeetCode 828. Unique Letter String」解题报告 | Tashi711的博客
No comments:
Post a Comment