Substrings of Size Three with Distinct Characters

Difficulty: Easy | Acceptance: 76.70% | Paid: No Topics: Hash Table, String, Sliding Window, Counting

A string is good if there are no repeated characters.

Given a string s, return the number of good substrings of length 3 in s.

Note that a substring is a contiguous sequence of characters in a string.

• Examples
• Constraints
• Brute Force
• Sliding Window with Set
• Direct Comparison

Examples

Example 1:

Input: s = "xyzzaz"
Output: 2
Explanation: There are 2 substrings of size 3 that have no repeated characters: "xyz" and "yza".

Example 2:

Input: s = "aababcabc"
Output: 8
Explanation: There are 8 substrings of size 3 that have no repeated characters: "aab", "aba", "bab", "abc", "bca", "cab", "abc", "bca".

Constraints

3 <= s.length <= 100
s[i] consists of lowercase English letters.

Brute Force

Intuition Iterate through the string and check every possible substring of length 3. For each substring, check if all characters are unique by comparing them or using a set.

Steps

• Initialize a counter to 0.
• Loop from index i = 0 to length - 3.
• Extract the substring s[i : i+3].
• Check if the characters at indices i, i+1, and i+2 are all distinct.
• If they are, increment the counter.
• Return the counter.

class Solution:
    def countGoodSubstrings(self, s: str) -> int:
        count = 0
        for i in range(len(s) - 2):
            if len(set(s[i:i+3])) == 3:
                count += 1
        return count

Complexity

• Time: O(n), where n is the length of the string. We iterate through the string once, and checking 3 characters is O(1).
• Space: O(1), we only use a few variables for storage.
• Notes: Simple and effective for small constraints.

Sliding Window with Set

Intuition Maintain a sliding window of size 3 using a Set to track unique characters. As we move the window one step to the right, we remove the leftmost character and add the new rightmost character.

Steps

• Initialize a counter and an empty Set.
• Iterate through the string with index i.
• Add s[i] to the Set.
• If the window size exceeds 3 (i.e., i >= 3), remove s[i-3] from the Set.
• If the window size is at least 3 (i.e., i >= 2) and the Set size is 3, increment the counter.
• Return the counter.

class Solution:
    def countGoodSubstrings(self, s: str) -> int:
        count = 0
        window = set()
        for i in range(len(s)):
            window.add(s[i])
            if i >= 3:
                window.remove(s[i-3])
            if i >= 2 and len(window) == 3:
                count += 1
        return count

Complexity

• Time: O(n), we traverse the string once.
• Space: O(1), the Set size is bounded by the window size (3).
• Notes: Generalizes well to larger window sizes k.

Direct Comparison

Intuition Since the window size is fixed and very small (3), we can simply check the three characters in the window directly without the overhead of a Set data structure.

Steps

• Initialize a counter to 0.
• Loop from index i = 0 to length - 3.
• Check if s[i] != s[i+1], s[i+1] != s[i+2], and s[i] != s[i+2].
• If all conditions are true, increment the counter.
• Return the counter.

class Solution:
    def countGoodSubstrings(self, s: str) -> int:
        count = 0
        for i in range(len(s) - 2):
            if s[i] != s[i+1] and s[i+1] != s[i+2] and s[i] != s[i+2]:
                count += 1
        return count

Complexity

• Time: O(n), single pass through the string.
• Space: O(1), no extra data structures used.
• Notes: Most efficient approach for this specific problem size.