难度: Medium
Submission
运行时间: 252 ms
内存: 16.4 MB
class Solution:
def numberOfSpecialSubstrings(self, s: str) -> int:
n = len(s)
last_occurrence = [-1] * 26 # 记录每个字符上一次出现的位置，初始化为-1
result = 0
left = 0 # 左指针
for right in range(n):
char = ord(s[right]) - ord('a') # 将字符映射为0-25的索引
# 如果当前字符之前已经出现过，则更新左指针的位置
if last_occurrence[char] >= left:
left = last_occurrence[char] + 1
# 更新当前字符上一次出现的位置
last_occurrence[char] = right
# 计算以当前右指针为结尾的特殊子字符串的数量
result += right - left + 1
return result
Explain
该题解使用了双指针（滑动窗口）的技巧来解决问题。首先定义一个数组 `last_occurrence` 来记录字符串中每个字符最后一次出现的位置。利用一个左指针 `left` 和一个右指针 `right` 遍历字符串。对于每个字符，如果它之前出现过，并且其上次出现的位置大于或等于当前左指针的位置，则将左指针移动到该字符上一次出现位置的下一个位置。然后更新该字符在 `last_occurrence` 中的位置。对于每个位置的右指针，计算从当前左指针到右指针之间的子字符串数量，并累加到结果中。
时间复杂度: O(n)
空间复杂度: O(1)
class Solution:
def numberOfSpecialSubstrings(self, s: str) -> int:
n = len(s)
last_occurrence = [-1] * 26 # 记录每个字符上一次出现的位置，初始化为-1
result = 0
left = 0 # 左指针
for right in range(n):
char = ord(s[right]) - ord('a') # 将字符映射为0-25的索引
# 如果当前字符之前已经出现过，则更新左指针的位置
if last_occurrence[char] >= left:
left = last_occurrence[char] + 1
# 更新当前字符上一次出现的位置
last_occurrence[char] = right
# 计算以当前右指针为结尾的特殊子字符串的数量
result += right - left + 1
return result
Explore
在初始化`last_occurrence`数组时，选择-1作为初始值是为了标记所有字符在开始遍历字符串`s`之前都未曾出现过。这个值在算法逻辑中起到关键作用：当我们检查某个字符时，如果它的`last_occurrence`值为-1，意味着该字符在当前`right`指针之前没有出现过，因此不需要移动`left`指针。这样可以保证`left`指针仅在必要时进行移动，从而正确地维护无重复字符的子字符串的边界。
当某个字符在`right`指针的当前位置再次出现时，为了确保从`left`到`right`的子字符串中没有重复字符，需要将`left`指针移动到该重复字符上一次出现的位置之后一个位置上（即`last_occurrence[char] + 1`）。这样做的目的是排除掉包含重复字符的子字符串区域，从而维护一个始终不包含重复字符的有效子字符串窗口。
对于每个右指针的位置，以该位置为结束点的所有可能的子字符串起始点为从`left`到`right`。因此，子字符串的数量等于`right`指针位置与`left`指针位置之间的距离加1（即`right - left + 1`）。这是因为每个这样的起始点都会与`right`指针位置形成一个唯一的子字符串。
是的，这种算法能有效地更新左指针以避免重复子字符串的计算。例如，字符串`'abca'`中，当处理到第二个`'a'`（位置3）时，`last_occurrence`数组记录的第一个`'a'`的位置是0。由于第二个`'a'`出现时，`left`指针位置是1，`last_occurrence[a]`是0，这大于当前`left`指针位置，因此将`left`指针更新为`last_occurrence[a] + 1`即1+1=2。这避免了从位置1开始的子字符串`'bca'`中的重复字符`'a'`的计算，确保所有计算的子字符串都是没有重复字符的。