E - 单一字符串dscg

Question

如果一个字符串仅有一个字母组成，那称这个字符串为单一字符串。比如 “A”、“BB”、“CC”为单一字符串，“AB”、“ABC”就不是。
给定一个长度为
n 的字符串
s，在它的所有子串中，有多少个不同的单一字符串? 比如字符串 “AABA”，有子串 “A”、“A”、“B”、“A”、“AA”、“AB”、“BA”、“AAB”、“ABA”、“AABA”。其中不同的单一字符串为 “A”、“B”、“AA” 三个。
输入
第一行一个正整数
（1≤n≤2∗10^5），表示字符串的长度。
第二行一个长度为
n 的字符串
s，仅由大写字母组成。
输出
一个整数，不同的单一字符串个数。c++

Answer 1

让阿豪来帮你解答，本回答参考chatgpt3.5编写提供，如果还有疑问可以评论或留言

算法思路： 对于一个单一字符串可以从任意位置开始，向左右两侧扩散得到所有的子串，因此可以枚举每个字符作为单一字符串的起点，统计扩散的子串中不同的单一字符串个数。 代码实现： 使用 set 存储不同的单一字符串。对于每个起点，向左右两侧扩散得到所有的子串，如果子串中的所有字符都与起点相同，则将该子串加入 set 中。 时间复杂度为 O(n^2log n)，空间复杂度为 O(nlog n)。 C++代码：