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 <= 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 \(\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\).

Python3JavaC++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

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;
    }
}

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;
    }
};

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
}

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;
}

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;
    }
}

Comments