E - 单一字符串iuytr

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，仅由大写字母组成。
输出
一个整数，不同的单一字符串个数。
时间限制1秒c++

Answer 1

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

思路： 由于题目要求统计所有子串中不同的单一字符串个数，我们可以考虑枚举所有子串，并将其中的单一字符串记录下来，最后再去重统计个数。 在枚举子串时，可以用两个指针$i,j$分别表示子串的起点和终点，用一个set（或unordered_set）记录当前子串中出现过的单一字符串，每次向右移动$j$并将$s[j]$加入set中，同时为了避免重复，每次向左移动$i$前也需要将$s[i]$从set中删除。如果每次从set中删除和添加元素的时间复杂度都是$O(1)$的话，遍历所有子串的时间复杂度就是$O(n^2)$。 然而，set的删除和添加操作的时间复杂度是$O(log\ n)$的，若使用set的话，就会导致算法的时间复杂度达到$O(n^2\ log\ n)$。因此我们需要采用一些方式，使得删除和添加操作的时间复杂度为$O(1)$，而unordered_set可以做到这一点。最终的时间复杂度就是$O(n^2)$的。 代码实现：