LeetCode 1876. Substrings of Size Three with Distinct Characters Solution in Java, C++, Python & More | Explanation + Code

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 <= 100
• s​​​​​​ 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 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 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 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 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.

PythonJavaC++GoTypeScriptPHP

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(code-box)

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; } }(code-box)

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; } };(code-box)

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 }(code-box)

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; }(code-box)

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; } }(code-box)