#1876

Easy

auto_awesomeSliding window with running state updates

LeetCode Problem Workspace

Substrings of Size Three with Distinct Characters

Count all substrings of length three in a string where each character is unique using sliding window techniques efficiently.

hash table string sliding window counting

Problem Statement

Given a string s consisting of lowercase English letters, return the total number of substrings of length three where all characters are distinct. A substring is considered 'good' if it contains no repeated characters.

Each substring occurrence is counted separately, even if it appears multiple times in s. For example, s = "xyzzaz" has substrings "xyz", "yzz", "zza", and "zaz"; only "xyz" is a good substring.

Examples

Example 1

Input: s = "xyzzaz"

Output: 1

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

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.

Solution Approach

Sliding Window with Set

Maintain a window of size three and use a set to track characters. Move the window forward by one character each time, updating the set, and count windows where the set size is three.

Iterative Comparison

Loop through the string and directly compare the three characters in each window for uniqueness. Increment a counter when all three are distinct. This avoids extra data structures but still follows the sliding window pattern.

Optimized Counting with Hash Table

Use a hash table to track character counts in the current window. Slide the window while updating counts efficiently. When the counts indicate three unique characters, increment the result. This reduces repeated set creation.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) since each character is visited once in the sliding window. Space complexity is O(1) because the set or hash table only tracks at most three characters at a time.

What Interviewers Usually Probe

Emphasis on sliding window to check all substrings of fixed size.
Looking for use of a set or hash table to quickly detect distinct characters.
Expect attention to counting every occurrence of a good substring without missing duplicates.

Common Pitfalls or Variants

Common pitfalls

Counting only unique substrings instead of all occurrences.
Forgetting to reset or update the set/hash table correctly when sliding the window.
Comparing characters incorrectly and miscounting substrings with repeated letters.

Follow-up variants

Count substrings of length k with distinct characters for any k > 1.
Return all good substrings instead of just counting them.
Check for substrings of size three that have exactly two distinct characters.

FAQ

What is a 'good' substring in Substrings of Size Three with Distinct Characters?

A 'good' substring has exactly three characters with no repetitions, meaning all characters are unique.

Can I use nested loops instead of a sliding window?

Yes, but a sliding window is more efficient for checking consecutive substrings of size three.

Does the order of characters matter?

Yes, the substring is contiguous in the original string, so the order matters for both uniqueness and counting.

How do I handle multiple occurrences of the same substring?

Each occurrence is counted separately; do not merge or remove duplicates when incrementing the result.

Is a set or hash table necessary for this sliding window problem?

Using a set or hash table simplifies checking for distinct characters and follows the sliding window pattern efficiently.

terminal

Solution

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.

1

2

3

4

5

6

7

8

9

10

11

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

Continue Practicing

#1897 redistribute characters to make all strings equal #1941 check if all characters have equal number of occurrences #1790 check if one string swap can make strings equal