0828. Count Unique Characters of All Substrings of a Given String¶
题目信息¶
- 题号:
0828
- 难度:
Hard
- 主题:
字符串、子串、唯一字符计数
- 原题:
- 重点:
对每个非空连续子串分别统计其中恰好出现一次的字符种类数,再把所有子串的统计值相加;重复出现的相同子串实例仍分别计数
题目重述¶
给定只包含大写英文字母的字符串 s。对于一个非空子串,若某个字符在该子串中恰好出现一次,则它是该子串的唯一字符;该子串的贡献值等于其唯一字符的种类数。
枚举 s 的所有非空连续子串,把每个子串的贡献值相加并返回总和。相同文本出现在不同起止下标时属于不同子串实例,需要分别计入。题目保证最终答案可以用 32 位有符号整数表示。
1 <= s.length <= 10^5,s 只包含大写英文字母。
自建示例¶
重复字符影响跨越它们的子串:
输入:s = "AAB"
输出:6
解释:三个单字符子串各贡献 1;"AA" 贡献 0,"AB" 贡献 2,"AAB" 只有 B 恰好出现一次、贡献 1,总和为 1 + 1 + 1 + 0 + 2 + 1 = 6。
字符串只有一个字符:
输入:s = "Z"
输出:1
解释:字符串长度达到题目允许的最小值,唯一的非空子串是 "Z",其中 Z 恰好出现一次,因此总贡献为 1。