网站建设合同报价,广西住房和城乡建设厅,品牌建设和品牌推广,太平洋保险网站做的这么烂题目链接 Leetcode.828 统计子串中的唯一字符 Rating #xff1a; 2034 题目描述
我们定义了一个函数 countUniqueChars(s)来统计字符串 s中的唯一字符#xff0c;并返回唯一字符的个数。
例如#xff1a;s LEETCODE#xff0c;则其中 L, 2034 题目描述
我们定义了一个函数 countUniqueChars(s)来统计字符串 s中的唯一字符并返回唯一字符的个数。
例如s LEETCODE则其中 L, T,C,O,D都是唯一字符因为它们只出现一次所以 countUniqueChars(s) 5。
本题将会给你一个字符串 s我们需要返回 countUniqueChars(t)的总和其中 t是 s的子字符串。输入用例保证返回值为 32 位整数。
注意某些子字符串可能是重复的但你统计时也必须算上这些重复的子字符串也就是说你必须统计 s的所有子字符串中的唯一字符。
示例 1 输入: s “ABC” 输出: 10 解释: 所有可能的子串为“A”,“B”,“C”,“AB”,“BC” 和 “ABC”。 其中每一个子串都由独特字符构成。 所以其长度总和为1 1 1 2 2 3 10 示例 2 输入: s “ABA” 输出: 8 解释: 除了 countUniqueChars(“ABA”) 1 之外其余与示例 1 相同。 示例 3 输入s “LEETCODE” 输出92 提示
1s.length1051 s.length 10^51s.length105s只包含大写英文字符
分析动态规划
对于 s的一个子串 s[0~i-1]我们分别计算添加 s[i]会增加多少唯一字符a和 减少多少唯一字符ba-b就是
此次 s[0~i-1]添加 s[i]的贡献。我们只需要对 s[0 ~ n - 1]用一样的逻辑即可。
我们下面讨论把 A添加到 BCADEAFG的贡献。 A本身 把 A添加到 G把 A添加到 FG都会增加 1个唯一字符。把 A添加到 AFG把 A添加到 EAFG把 A添加到 DEAFG 都会减少 1个唯一字符。把 A添加到 ADEAFG把 CADEAFG添加到 BCADEAFG把 A添加到 DEAFG 都不会发生变化。
我们发现当添加一个字符 s[i]时
增加的贡献i - s[i]上一次出现的位置减少的贡献s[i]上一次出现的位置 - s[i]上上一次出现的位置
我们用 pre记录 s[i]上一次出现的位置用 prepre记录 s[i]上上一次出现的位置。
添加 s[i]后总的变化量为(i - pre[s[i]]) - (pre[s[i]] - prepre[s[i]])
我们每次都用 total维护 以 s[i]结尾的 唯一字符数量。
每次都添加到答案 ans上。
时间复杂度 O(n)O(n)O(n)
C代码
class Solution {
public:int uniqueLetterString(string s) {int n s.size();int pre[26],prepre[26];memset(pre,-1,sizeof pre);memset(prepre,-1,sizeof prepre);int ans 0 , total 0;;for(int i 0;i n;i){int t s[i] - A;total i - 2 * pre[t] prepre[t];ans total;prepre[t] pre[t];pre[t] i;}return ans;}
};Java代码
class Solution {public int uniqueLetterString(String s) {int n s.length();int[] pre new int[26];int[] prepre new int[26];Arrays.fill(pre,-1);Arrays.fill(prepre,-1);int ans 0;int total 0;for(int i 0;i n;i){int t s.charAt(i) - A;total (i - pre[t]) - (pre[t] - prepre[t]);ans total;prepre[t] pre[t];pre[t] i;}return ans;}
}
