难度: Hard
给你一个字符串 text ，请你返回满足下述条件的 不同 非空子字符串的数目：
a + a，其中 a 是某个字符串）。例如，abcabc 就是 abc 和它自身连接形成的。
示例 1：
输入：text = "abcabcabc" 输出：3 解释：3 个子字符串分别为 "abcabc"，"bcabca" 和 "cabcab" 。
示例 2：
输入：text = "leetcodeleetcode" 输出：2 解释：2 个子字符串为 "ee" 和 "leetcodeleetcode" 。
提示：
1 <= text.length <= 2000text 只包含小写英文字母。运行时间: 538 ms
内存: 16.8 MB
class Solution:
def distinctEchoSubstrings(self, text: str) -> int:
res = defaultdict(list)
ans = set()
for i, t in enumerate(text):
for index in res[t]:
if index + 1 >= i - index:
if text[index - i + index + 1: index + 1] == text[index + 1: i + 1]:
ans.add(text[index + 1: i + 1])
res[t].append(i)
return len(ans)
该题解的核心思路是利用哈希表来记录每个字符出现的所有位置，然后依此判断是否存在形如a+a的子字符串。具体实现中，遍历字符串的每个字符，利用一个字典res存储每个字符和其出现位置的列表。对于当前字符t和位置i，检查之前所有t出现的位置，判断在这些位置之间的字符串是否可以形成a+a。这是通过比较两个相邻位置间的字符串是否相同来完成的。如果相同，则将该字符串加入到结果集合ans中。最终，返回集合ans的大小，即不同的符合条件的子字符串数目。
时间复杂度: O(n^3)
空间复杂度: O(n)
class Solution:
def distinctEchoSubstrings(self, text: str) -> int:
res = defaultdict(list) # 存储每个字符出现的位置
ans = set() # 存储符合条件的子字符串，自动去重
for i, t in enumerate(text): # 遍历每个字符及其索引
for index in res[t]: # 对当前字符的每个先前出现位置进行检查
if index + 1 >= i - index: # 确保不越界
if text[index - i + index + 1: index + 1] == text[index + 1: i + 1]: # 比较两段是否相同
ans.add(text[index + 1: i + 1]) # 若相同，则添加到结果集
res[t].append(i) # 更新当前字符的位置列表
return len(ans) # 返回不同子字符串的数量
在给定的算法中，我们寻找形式为a+a的字符串，这意味着字符串由两个相同的部分a组成。通过记录每个字符出现的所有位置，我们可以找到所有可能的相同字符对的位置组合。对于字符t的任意两个相邻出现位置index和i（index < i），如果在index和i之间的字符串长度与从index到i的长度相等且内容相同，那么这部分字符串就是形式为a+a。因此，通过比较这两个相邻位置间的字符串是否相同，可以有效地判断是否形成了所需的子字符串结构。
使用集合(set)来存储符合条件的子字符串的主要目的是利用集合的自动去重特性，这可以有效地防止同一个子字符串被多次计数。集合在这种情况下提供了简单且高效的去重方法。尽管其他数据结构例如列表(list)也可以用来存储这些子字符串，但它们则需要额外的操作来保证元素的唯一性，如使用循环来检查重复或者在添加前进行查找，这会增加时间复杂性。另一种选择是哈希表（如Python中的字典），它同样可以达到去重的目的，但对于本问题而言，集合更为直接和高效。
这个条件确保了在比较两个相邻位置间的字符串内容前，后一个位置i与前一个位置index之间有足够的字符来构成一个可能的a+a结构。具体来说，`i - index`是两个相邻位置之间的距离，而`index + 1 >= i - index`确保了从index开始的字符串长度至少与index到i之间的距离相等，这是形成a+a结构的基本要求。如果没有这个条件，可能会导致字符串比较时越界，或者比较不等长的字符串，从而造成逻辑错误。
哈希表res存储每个字符出现的所有位置，在字符分布较均匀或字符串较短时效率较高，因为这样可以较快地访问和更新每个字符的位置列表。当字符串较长且某些字符非常频繁地出现时，效率可能较低。在这种情况下，每个字符的位置列表可能变得非常长，导致每次更新位置列表和检查可能的a+a结构时耗时增加。此外，如果字符很少重复，那么哈希表的优势不明显，因为大部分位置列表都非常短。