LeetCode每日一题——828. 统计子串中的唯一字符

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

题目

我们定义了一个函数 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

提示:

1 <= s.length <= 10^5

s 只包含大写英文字符

思路

首先想到的是dfs求出所有子串,然后再判断每一个字段的重复字符,最后相加,然后就超时了…

一种比较简单的做法是,从A-Z遍历所有的字母,对与A-Z的每一个字符i,向后寻找相同的字符j,求出二者下标间距j-i,累加这个间距即可。

题解

class Solution:
    def uniqueLetterString(self, s: str) -> int:
        n = len(s)
        ans = 0
        for ch in string.ascii_uppercase:
          # 左右指针
            l = r = -1
            for j in range(n):
                if s[j] == ch:
                    l, r = r, j 
                # 累加间距即可
                ans += r - l 
        return ans 
目录
相关文章
|
Unix Shell Linux
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
186 6
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
|
11月前
|
存储 算法
Leetcode第三题(无重复字符的最长子串)
这篇文章介绍了解决LeetCode第三题“无重复字符的最长子串”的算法,使用滑动窗口技术来找出给定字符串中最长的不含重复字符的子串,并提供了详细的代码实现和解释。
548 0
Leetcode第三题(无重复字符的最长子串)
LeetCode第3题无重复字符的最长子串
该文章介绍了 LeetCode 第 3 题无重复字符的最长子串的解法,通过使用 HashSet 记录不重复的子元素,以每个字符开头遍历字符串,遇到重复字符则重新计算,最终找到最长子串,同时提到可以考虑使用 HashMap 降低复杂度。
LeetCode第3题无重复字符的最长子串
|
存储 算法 测试技术
力扣经典150题第三十三题:最小覆盖子串
力扣经典150题第三十三题:最小覆盖子串
121 1
|
存储 算法 Java
LeetCode初级算法题:反转链表+统计N以内的素数+删除排序数组中的重复项Java详解
LeetCode初级算法题:反转链表+统计N以内的素数+删除排序数组中的重复项Java详解
113 0
|
算法
【LeetCode刷题】滑动窗口解决问题:串联所有单词的子串(困难)、最小覆盖子串(困难)
【LeetCode刷题】滑动窗口解决问题:串联所有单词的子串(困难)、最小覆盖子串(困难)
108 1
|
存储 算法
经典的滑动窗口的题目 力扣 2799. 统计完全子数组的数目(面试题)
经典的滑动窗口的题目 力扣 2799. 统计完全子数组的数目(面试题)
140 0
|
索引
821.字符的最短距离-力扣(LeetCode)
821.字符的最短距离-力扣(LeetCode)
131 0
|
算法 测试技术 索引
力扣经典150题第三十二题:串联所有单词的子串
力扣经典150题第三十二题:串联所有单词的子串
99 0
|
存储 算法 程序员
力扣经典150题第三十一题:无重复字符的最长子串
力扣经典150题第三十一题:无重复字符的最长子串
91 0

热门文章

最新文章