You are given a string s consisting only of lowercase English letters. We call a substring special if it contains no character which has occurred at least twice (in other words, it does not contain a repeating character). Your task is to count the number of special substrings. For example, in the string "pop", the substring "po" is a special substring, however,
"pop" is not special (since 'p' has occurred twice).
Return the number ofspecial substrings.
A substring is a contiguous sequence of characters within a string. For example, "abc" is a substring of "abcd", but "acd" is not.
Input: s ="abcd"Output: 10Explanation: Since each character occurs once, every substring is a special substring. We have 4 substrings of length one,3 of length two,2 of length three, and 1 substring of length four. So overall there are 4+3+2+1=10 special substrings.
Example 2:
1
2
3
Input: s ="ooo"Output: 3Explanation: Any substring with a length of at least two contains a repeating character. So we have to count the number of substrings of length one, which is3.
Example 3:
1
2
3
4
5
6
Input: s ="abab"Output: 7Explanation: Special substrings are as follows(sorted by their start positions):Special substrings of length 1:"a","b","a","b"Special substrings of length 2:"ab","ba","ab"And it can be shown that there are no special substrings with a length of at least three. So the answer would be 4+3=7.
A substring without repeating characters is a substring where all characters are unique. For each position, we can use a sliding window to expand as far as possible to the right without repeating any character, and count all such substrings efficiently.
classSolution {
public:longlong countSpecialSubstrings(string s) {
int n = s.size();
vector<int> last(26, -1);
longlong ans =0;
int l =0;
for (int r =0; r < n; ++r) {
l = max(l, last[s[r] -'a'] +1);
ans += r - l +1;
last[s[r] -'a'] = r;
}
return ans;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
typeSolutionstruct{}
func (Solution) CountSpecialSubstrings(sstring) int64 {
n:= len(s)
last:= make([]int, 26)
fori:=rangelast {
last[i] = -1 }
varansint64l:=0forr:=0; r < n; r++ {
iflast[s[r]-'a']+1 > l {
l = last[s[r]-'a'] +1 }
ans+= int64(r-l+1)
last[s[r]-'a'] = r }
returnans}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
classSolution {
publiclongcountSpecialSubstrings(String s) {
int n = s.length();
int[] last =newint[26];
Arrays.fill(last, -1);
long ans = 0;
int l = 0;
for (int r = 0; r < n; ++r) {
l = Math.max(l, last[s.charAt(r) -'a']+ 1);
ans += r - l + 1;
last[s.charAt(r) -'a']= r;
}
return ans;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
classSolution {
funcountSpecialSubstrings(s: String): Long {
val n = s.length
val last = IntArray(26) { -1 }
var ans = 0Lvar l = 0for (r in0 until n) {
l = maxOf(l, last[s[r] - 'a'] + 1)
ans += (r - l + 1)
last[s[r] - 'a'] = r
}
return ans
}
}
1
2
3
4
5
6
7
8
9
10
11
classSolution:
defcountSpecialSubstrings(self, s: str) -> int:
n = len(s)
last = [-1] *26 ans =0 l =0for r in range(n):
l = max(l, last[ord(s[r]) - ord('a')] +1)
ans += r - l +1 last[ord(s[r]) - ord('a')] = r
return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
impl Solution {
pubfncount_special_substrings(s: String) -> i64 {
let n = s.len();
let s = s.as_bytes();
letmut last =vec![-1; 26];
letmut ans =0i64;
letmut l =0;
for r in0..n {
l = l.max((last[(s[r] -b'a') asusize] +1) asusize);
ans += (r - l +1) asi64;
last[(s[r] -b'a') asusize] = r asi32;
}
ans
}
}