专栏首页Michael阿明学习之路LeetCode 828. 统计子串中的唯一字符(中心扩展)

LeetCode 828. 统计子串中的唯一字符(中心扩展)

1. 题目

我们定义了一个函数 countUniqueChars(s) 来统计字符串 s 中的唯一字符,并返回唯一字符的个数。

例如:s = “LEETCODE” ,则其中 “L”, “T”,“C”,“O”,“D” 都是唯一字符,因为它们只出现一次,所以 countUniqueChars(s) = 5 。

本题将会给你一个字符串 s ,我们需要返回 countUniqueChars(t) 的总和,其中 t 是 s 的子字符串。 注意,某些子字符串可能是重复的,但你统计时也必须算上这些重复的子字符串(也就是说,你必须统计 s 的所有子字符串中的唯一字符)。

由于答案可能非常大,请将结果 mod 10 ^ 9 + 7 后再返回。

示例 1:
输入: "ABC"
输出: 10
解释: 所有可能的子串为:"A","B","C","AB","BC" 和 "ABC"。
     其中,每一个子串都由独特字符构成。
     所以其长度总和为:1 + 1 + 1 + 2 + 2 + 3 = 10
     
示例 2:
输入: "ABA"
输出: 8
解释: 除了 countUniqueChars("ABA") = 1 之外,其余与示例 1 相同。

示例 3:
输入:s = "LEETCODE"
输出:92
 
提示:
0 <= s.length <= 10^4
s 只包含大写英文字符

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/count-unique-characters-of-all-substrings-of-a-given-string 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

2. 解题

类似题目:LeetCode 1180. 统计只含单一字母的子串

  • 对每个字符进行考虑,找到每个字符前后同样的字符的位置
  • 左右两边的数量相乘即为,该字符可以出现在子串的次数
class Solution {	//C++
public:
    int uniqueLetterString(string s) {
        int i, j, k, count = 0;
        for(j = 0; j < s.size(); ++j)
        {
        	i = j-1, k = j+1;
        	while(i>=0 && s[i] != s[j])
        		i--;
        	while(k<s.size() && s[j] != s[k])
        		k++;
        	count = (count+(j-i)*(k-j))%1000000007;
        }
        return count;
    }
};

64 ms 7.2 MB

另一种方法,预先存储下来相同字符的位置

class Solution {
public:
    int uniqueLetterString(string s) {
        int count = 0;
        unordered_map<char,set<int>> m;
        for(int i = 0; i < s.size(); ++i)
        {
            m[s[i]].insert(i);
        }
        int lenl, lenr;
        for(int i = 0; i < s.size(); ++i)
        {
            auto it = m[s[i]].find(i);
            if(it == m[s[i]].begin())
                lenl = i+1;
            else
            {
                auto itl = it;
                itl--;
                lenl = i-*(itl);
            }
            if(it == --m[s[i]].end())
                lenr = s.size()-i;
            else
            {
                it++;
                lenr = *(it)-i;
            }
            count = (count+lenl*lenr)%1000000007;
        }
        return count;
    }
};

276 ms 21.9 MB

python3 解答

class Solution:
    def uniqueLetterString(self, s: str) -> int:
        count = 0
        for j in range(len(s)):
            i = j-1 
            k = j+1
            while i>=0 and s[i]!=s[j]:
                i -= 1
            while k<len(s) and s[j]!=s[k]:
                k += 1
            count = (count+(j-i)*(k-j))%1000000007
        return count

804 ms 13.7 MB

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode 791. 自定义字符串排序(map)

    S 已经根据某种规则进行了排序。我们要根据S中的字符顺序对T进行排序。更具体地说,如果S中x在y之前出现,那么返回的字符串中x也应出现在y之前。

    Michael阿明
  • LeetCode 762. 二进制表示中质数个计算置位

    给定两个整数 L 和 R ,找到闭区间 [L, R] 范围内,计算置位位数为质数的整数个数。

    Michael阿明
  • LeetCode 423. 从英文中重建数字(找规律)

    给定一个非空字符串,其中包含字母顺序打乱的英文单词表示的数字0-9。按升序输出原始的数字。

    Michael阿明
  • LeetCode 3: 无重复字符的最长子串

    Given a string, find the length of the longest substring without repeating chara...

    爱写bug
  • Leetcode 1207. 独一无二的出现次数(C语言)

    Kindear
  • leetcode474. Ones and Zeroes

    先是用深度优先遍历的思想进行了实现,结果很明显是超时了。接着采用动态规划的思想,其实这题就是背包问题的一个演化。假设已知道m个0和n个1能够从数组中前i个元素最...

    眯眯眼的猫头鹰
  • 漫画:什么是计数排序?

    计数排序(Counting Sort)是一种针对于特定范围之间的整数进行排序的算法。它通过统计给定数组中不同元素的数量(类似于哈希映射),然后对映射后的数组进行...

    灵魂画师牧码
  • 漫画:什么是计数排序?

    计数排序(Counting Sort)是一种针对于特定范围之间的整数进行排序的算法。它通过统计给定数组中不同元素的数量(类似于哈希映射),然后对映射后的数组进行...

    五分钟学算法
  • LeetCode 74 & 240 Search a 2D Matrix I,II

    一个矩阵,每一行都是递增顺序,并且下一列比上一列的最大值要大。给定一个目标值,判断这个target是否在这个矩阵中。

    大学里的混子
  • 每天一道leetcode240-在二维数组中搜索n升级版

    https://leetcode.com/problems/search-a-2d-matrix-ii/

    乔戈里

扫码关注云+社区

领取腾讯云代金券