2743. Count Substrings Without Repeating Character π
Description
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 of special substrings.
A substring is a contiguous sequence of characters within a string. For example, "abc"
is a substring of "abcd"
, but "acd"
is not.
Example 1:
Input: s = "abcd" Output: 10 Explanation: 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:
Input: s = "ooo" Output: 3 Explanation: 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 is 3.
Example 3:
Input: s = "abab" Output: 7 Explanation: 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.
Constraints:
1 <= s.length <= 105
s
consists of lowercase English letters
Solutions
Solution 1: Counting + Two Pointers
We use two pointers $j$ and $i$ to represent the left and right boundaries of the current substring, and an array $cnt$ of length $26$ to count the occurrence of each character in the current substring. We traverse the string from left to right. Each time we traverse to position $i$, we increase the occurrence of $s[i]$, and then check whether $s[i]$ appears at least twice. If so, we need to decrease the occurrence of $s[j]$ and move $j$ one step to the right, until the occurrence of $s[i]$ does not exceed once. In this way, we get the length of the longest special substring ending with $s[i]$, which is $i - j + 1$, so the number of special substrings ending with $s[i]$ is $i - j + 1$. Finally, we add up the number of special substrings ending at each position to get the answer.
The time complexity is $O(n)$, and the space complexity is $O(C)$. Here, $n$ is the length of the string $s$, and $C$ is the size of the character set. In this problem, the character set consists of lowercase English letters, so $C = 26$.
1 2 3 4 5 6 7 8 9 10 11 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
|