0828. Count Unique Characters of All Substrings of a Given String

题目信息

题号:

0828

难度:

Hard

主题:

字符串、子串、唯一字符计数

原题:

LeetCode 0828

重点:

对每个非空连续子串分别统计其中恰好出现一次的字符种类数,再把所有子串的统计值相加;重复出现的相同子串实例仍分别计数

题目重述

给定只包含大写英文字母的字符串 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。