1876. Substrings of Size Three with Distinct Characters
Description
A string is good if there are no repeated characters.
Given a string s, return the number of good substrings of length three in s.
Note that if there are multiple occurrences of the same substring, every occurrence should be counted.
A substring is a contiguous sequence of characters in a string.
Example 1:
Input: s = "xyzzaz" Output: 1 Explanation: There are 4 substrings of size 3: "xyz", "yzz", "zza", and "zaz". The only good substring of length 3 is "xyz".
Example 2:
Input: s = "aababcabc" Output: 4 Explanation: There are 7 substrings of size 3: "aab", "aba", "bab", "abc", "bca", "cab", and "abc". The good substrings are "abc", "bca", "cab", and "abc".
Constraints:
1 <= s.length <= 100s consists of lowercase English letters.
Solutions
Solution 1: Sliding Window
We can maintain a sliding window such that the characters within the window are not repeated. Initially, we use a binary integer $\textit{mask}$ of length $26$ to represent the characters within the window, where the $i$-th bit being $1$ indicates that character $i$ has appeared in the window, otherwise it indicates that character $i$ has not appeared in the window.
Then, we traverse the string $s$. For each position $r$, if $\textit{s}[r]$ has appeared in the window, we need to move the left boundary $l$ of the window to the right until there are no repeated characters in the window. After this, we add $\textit{s}[r]$ to the window. At this point, if the length of the window is greater than or equal to $3$, then we have found a good substring of length $3$ ending at $\textit{s}[r]$.
After the traversal, we have found the number of all good substrings.
The time complexity is $O(n)$, where $n$ is the length of the string $s$. The space complexity is $O(1)$.
This solution can be extended to find the number of good substrings of length $k$.
Python3
class Solution:
def countGoodSubstrings(self, s: str) -> int:
ans = mask = l = 0
for r, x in enumerate(map(lambda c: ord(c) - 97, s)):
while mask >> x & 1:
y = ord(s[l]) - 97
mask ^= 1 << y
l += 1
mask |= 1 << x
ans += int(r - l + 1 >= 3)
return ans
Java
class Solution {
public int countGoodSubstrings(String s) {
int ans = 0;
int n = s.length();
for (int l = 0, r = 0, mask = 0; r < n; ++r) {
int x = s.charAt(r) - 'a';
while ((mask >> x & 1) == 1) {
int y = s.charAt(l++) - 'a';
mask ^= 1 << y;
}
mask |= 1 << x;
ans += r - l + 1 >= 3 ? 1 : 0;
}
return ans;
}
}
C++
class Solution {
public:
int countGoodSubstrings(string s) {
int ans = 0;
int n = s.length();
for (int l = 0, r = 0, mask = 0; r < n; ++r) {
int x = s[r] - 'a';
while ((mask >> x & 1) == 1) {
int y = s[l++] - 'a';
mask ^= 1 << y;
}
mask |= 1 << x;
ans += r - l + 1 >= 3 ? 1 : 0;
}
return ans;
}
};
Go
func countGoodSubstrings(s string) (ans int) {
mask, l := 0, 0
for r, c := range s {
x := int(c - 'a')
for (mask>>x)&1 == 1 {
y := int(s[l] - 'a')
l++
mask ^= 1 << y
}
mask |= 1 << x
if r-l+1 >= 3 {
ans++
}
}
return
}
TypeScript
function countGoodSubstrings(s: string): number {
let ans = 0;
const n = s.length;
for (let l = 0, r = 0, mask = 0; r < n; ++r) {
const x = s.charCodeAt(r) - 'a'.charCodeAt(0);
while ((mask >> x) & 1) {
const y = s.charCodeAt(l++) - 'a'.charCodeAt(0);
mask ^= 1 << y;
}
mask |= 1 << x;
ans += r - l + 1 >= 3 ? 1 : 0;
}
return ans;
}
PHP
class Solution {
/**
* @param String $s
* @return Integer
*/
function countGoodSubstrings($s) {
$ans = 0;
$n = strlen($s);
$l = 0;
$r = 0;
$mask = 0;
while ($r < $n) {
$x = ord($s[$r]) - ord('a');
while (($mask >> $x) & 1) {
$y = ord($s[$l++]) - ord('a');
$mask ^= 1 << $y;
}
$mask |= 1 << $x;
if ($r - $l + 1 >= 3) {
$ans++;
}
$r++;
}
return $ans;
}
}