class Solution {
public:
int numberOfSpecialSubstrings(string s) {
}
};
2743. 计算没有重复字符的子字符串数量
给定你一个只包含小写英文字母的字符串 s 。如果一个子字符串不包含任何字符至少出现两次（换句话说，它不包含重复字符），则称其为 特殊 子字符串。你的任务是计算 特殊 子字符串的数量。例如，在字符串 "pop" 中，子串 "po" 是一个特殊子字符串，然而 "pop" 不是 特殊 子字符串（因为 'p' 出现了两次）。
返回 特殊 子字符串的数量。
子字符串 是指字符串中连续的字符序列。例如，"abc" 是 "abcd" 的一个子字符串，但 "acd" 不是。
示例 1：
输入：s = "abcd" 输出：10 解释：由于每个字符只出现一次，每个子串都是特殊子串。长度为 1 的子串有 4 个，长度为 2 的有 3 个，长度为 3 的有 2 个，长度为 4 的有 1 个。所以一共有 4 + 3 + 2 + 1 = 10 个特殊子串。
示例 2：
输入：s = "ooo" 输出：3 解释：任何长度至少为 2 的子串都包含重复字符。所以我们要计算长度为 1 的子串的数量，即 3 个。
示例 3：
输入：s = "abab" 输出：7 解释：特殊子串如下（按起始位置排序）： 长度为 1 的特殊子串："a", "b", "a", "b" 长度为 2 的特殊子串："ab", "ba", "ab" 并且可以证明没有长度至少为 3 的特殊子串。所以答案是4 + 3 = 7。
提示：
1 <= s.length <= 105s 只包含小写英文字母。原站题解
java 解法, 执行用时: 8 ms, 内存消耗: 43.5 MB, 提交时间: 2023-10-21 20:14:24
class Solution {
public int numberOfSpecialSubstrings(String s) {
int ans = 0;
int[] pos = new int[26];
Arrays.fill(pos,-1);
int left = 0;
for (int right = 0; right < s.length(); right++) {
int v = s.charAt(right) - 'a';
left = Math.max(left,pos[v] + 1);
ans += (right-left+1);
pos[v] = right;
}
return ans;
}
}
python3 解法, 执行用时: 496 ms, 内存消耗: 16.5 MB, 提交时间: 2023-10-21 20:13:33
class Solution:
def numberOfSpecialSubstrings(self, s: str) -> int:
ss, res, srt = set(), 0, 0
for i, v in enumerate(s):
while v in ss:
ss.remove(s[srt])
srt += 1
ss.add(v)
res += i - srt + 1
return res
java 解法, 执行用时: 138 ms, 内存消耗: 43.3 MB, 提交时间: 2023-10-21 20:13:20
class Solution {
public int numberOfSpecialSubstrings(String s) {
Map<Character, Integer> map = new HashMap<>();
int res = 0;
int l = 0;
//# 从右指针开始
for(int r = 0; r < s.length(); r++){
map.put(s.charAt(r), map.getOrDefault(s.charAt(r) , 0) + 1);
//# 当发现子串不符合要求调整至符合要求
while(map.get(s.charAt(r)) == 2){
map.put(s.charAt(l) , map.get(s.charAt(l)) - 1);
l++;
}
//# 可以根据 a 符合 ab符合， 那么后面如果出现 abc也符合。
res = res + r - l + 1;
}
return res;
}
}