Problem Description

You need to find how many substrings of length exactly 3 in a given string s contain no repeated characters.

A substring is considered "good" if all its characters are unique (no character appears more than once). You're specifically looking for good substrings that have exactly 3 characters.

For example:

• In the string "xyzzaz", the substring "xyz" is good (all characters are different)
• The substring "yzz" is not good (the character 'z' appears twice)

The task is to count all possible good substrings of length 3 in the string. If the same good substring appears multiple times at different positions, each occurrence should be counted separately.

Key points:

• A substring must be contiguous (consecutive characters from the original string)
• The substring must have exactly 3 characters
• All 3 characters in the substring must be different from each other
• Return the total count of such substrings

Intuition

The key insight is that we can use a sliding window to efficiently track unique characters. Instead of checking every possible substring of length 3 separately, we can maintain a window that always contains only unique characters.

Think of it this way: as we move through the string, we want to keep track of the longest stretch of unique characters ending at each position. If at position r we have at least 3 unique characters in our current window, then the substring of length 3 ending at position r is "good".

The clever part is using a bitmask to track which characters are in our window. Since we only have lowercase letters (26 possible characters), we can use a single integer where each bit represents whether a specific character is present. For example, if bit 0 is set, it means 'a' is in the window; if bit 1 is set, 'b' is in the window, and so on.

When we encounter a character that's already in our window (its bit is already set in the mask), we need to shrink the window from the left side. We keep removing characters from the left until the duplicate is removed. This ensures our window always contains unique characters.

At each position, after maintaining the window of unique characters, we check if the window size is at least 3. If it is, we've found a good substring of length 3 ending at the current position. The expression r - l + 1 >= 3 checks this condition, where r is the right boundary and l is the left boundary of our window.

This approach is efficient because we visit each character at most twice - once when adding it to the window and once when removing it, giving us linear time complexity.

Learn more about Sliding Window patterns.

Solution Approach

We implement a sliding window approach with a bitmask to track unique characters in the window.

Step 1: Initialize Variables

• ans: Counter for good substrings
• mask: Bitmask to track which characters are in the window (initially 0)
• l: Left boundary of the sliding window (initially 0)

Step 2: Process Each Character We iterate through the string with index r and convert each character to a number x (0 for 'a', 1 for 'b', etc.) using ord(c) - 97.

Step 3: Handle Duplicates Before adding the current character to the window, we check if it's already present using mask >> x & 1:

• If the x-th bit is 1, the character is already in the window
• We shrink the window from the left by:
  • Getting the character at position l and converting it to number y
  • Removing it from the mask using XOR: mask ^= 1 << y
  • Moving the left boundary: l += 1
• This continues until the duplicate is removed

Step 4: Add Current Character After ensuring no duplicates, we add the current character to the window:

• Set the x-th bit in the mask: mask |= 1 << x

Step 5: Count Good Substrings If the window size r - l + 1 is at least 3, we have a good substring of length 3 ending at position r:

• We increment ans by 1 using ans += int(r - l + 1 >= 3)

Bitmask Operations Explained:

• 1 << x: Creates a number with only the x-th bit set
• mask >> x & 1: Checks if the x-th bit in mask is 1
• mask |= 1 << x: Sets the x-th bit to 1 (adds character)
• mask ^= 1 << y: Flips the y-th bit (removes character)

The algorithm ensures that at each position, we maintain the longest window of unique characters ending at that position. If this window has at least 3 characters, we've found a good substring of length 3.

Time Complexity: O(n) where n is the length of string s, as each character is visited at most twice.

Space Complexity: O(1) as we only use a fixed amount of extra space regardless of input size.

Example Walkthrough

Let's trace through the string "aababcabc" to count good substrings of length 3.

Initial Setup:

• ans = 0 (count of good substrings)
• mask = 0 (binary: 000000, no characters in window)
• l = 0 (left boundary)

Step-by-step execution:

r = 0, character = 'a':

• Convert 'a' to x = 0
• Check if 'a' is in window: mask >> 0 & 1 = 0 (not present)
• Add 'a': mask = 000001 (bit 0 set)
• Window = "a", size = 1 (< 3)
• ans = 0

r = 1, character = 'a':

• Convert 'a' to x = 0
• Check if 'a' is in window: mask >> 0 & 1 = 1 (present!)
• Remove characters from left until 'a' is gone:
  • Remove s[0]='a': mask ^= 1 << 0, mask becomes 000000
  • Move left: l = 1
• Add current 'a': mask = 000001
• Window = "a", size = 1 (< 3)
• ans = 0

r = 2, character = 'b':

• Convert 'b' to x = 1
• Check if 'b' is in window: mask >> 1 & 1 = 0 (not present)
• Add 'b': mask = 000011 (bits 0,1 set)
• Window = "ab", size = 2 (< 3)
• ans = 0

r = 3, character = 'a':

• Convert 'a' to x = 0
• Check if 'a' is in window: mask >> 0 & 1 = 1 (present!)
• Remove characters from left until 'a' is gone:
  • Remove s[1]='a': mask ^= 1 << 0, mask becomes 000010
  • Move left: l = 2
• Add current 'a': mask = 000011
• Window = "ba", size = 2 (< 3)
• ans = 0

r = 4, character = 'b':

• Convert 'b' to x = 1
• Check if 'b' is in window: mask >> 1 & 1 = 1 (present!)
• Remove characters from left until 'b' is gone:
  • Remove s[2]='b': mask ^= 1 << 1, mask becomes 000001
  • Move left: l = 3
• Add current 'b': mask = 000011
• Window = "ab", size = 2 (< 3)
• ans = 0

r = 5, character = 'c':

• Convert 'c' to x = 2
• Check if 'c' is in window: mask >> 2 & 1 = 0 (not present)
• Add 'c': mask = 000111 (bits 0,1,2 set)
• Window = "abc", size = 3 (= 3) ✓
• Found good substring "abc"!
• ans = 1

r = 6, character = 'a':

• Convert 'a' to x = 0
• Check if 'a' is in window: mask >> 0 & 1 = 1 (present!)
• Remove characters from left until 'a' is gone:
  • Remove s[3]='a': mask ^= 1 << 0, mask becomes 000110
  • Move left: l = 4
• Add current 'a': mask = 000111
• Window = "bca", size = 3 (= 3) ✓
• Found good substring "bca"!
• ans = 2

r = 7, character = 'b':

• Convert 'b' to x = 1
• Check if 'b' is in window: mask >> 1 & 1 = 1 (present!)
• Remove characters from left until 'b' is gone:
  • Remove s[4]='b': mask ^= 1 << 1, mask becomes 000101
  • Move left: l = 5
• Add current 'b': mask = 000111
• Window = "cab", size = 3 (= 3) ✓
• Found good substring "cab"!
• ans = 3

r = 8, character = 'c':

• Convert 'c' to x = 2
• Check if 'c' is in window: mask >> 2 & 1 = 1 (present!)
• Remove characters from left until 'c' is gone:
  • Remove s[5]='c': mask ^= 1 << 2, mask becomes 000011
  • Move left: l = 6
• Add current 'c': mask = 000111
• Window = "abc", size = 3 (= 3) ✓
• Found good substring "abc"!
• ans = 4

Final Result: The string "aababcabc" contains 4 good substrings of length 3: "abc" (at position 3-5), "bca" (at position 4-6), "cab" (at position 5-7), and "abc" (at position 6-8).

Solution Implementation

Time and Space Complexity

Time Complexity: O(n) where n is the length of string s.

The algorithm uses a sliding window approach with two pointers (l and r). The right pointer r iterates through each character exactly once. The left pointer l moves forward only when there's a duplicate character in the current window. In the worst case, each character can cause the left pointer to move at most once throughout the entire execution. Therefore, both pointers combined traverse the string at most 2n times, resulting in O(n) time complexity.

Space Complexity: O(1)

The algorithm uses a fixed amount of extra space:

• mask: An integer used as a bitmask to track which characters are present in the current window. Since there are only 26 lowercase letters, this requires constant space.
• ans, l, r, x, y: Integer variables that use constant space.

The bitmask approach stores character presence information in a single integer regardless of input size, making the space complexity constant.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall: Misunderstanding the Window Size Logic

The current solution has a critical flaw - it counts ALL windows of size 3 or greater, not just windows of exactly size 3. When right - left + 1 >= 3, the code increments the counter, but this doesn't guarantee we're counting a substring of exactly length 3.

Why this is wrong:

• If we have a window "abcd" (size 4), the condition right - left + 1 >= 3 is true
• The code would count this as a good substring, but we need substrings of EXACTLY length 3
• We should only be counting "abc", "bcd" etc., not considering the entire window of size 4

Example where this fails: For string "abcde":

• When we reach index 2 (character 'c'), window is "abc" - count should increase by 1
• When we reach index 3 (character 'd'), window is "abcd" - but this counts the window of size 4, not a substring of size 3
• When we reach index 4 (character 'e'), window is "abcde" - again counting window of size 5

Solution: Check for Exactly 3 Characters

Approach 1: Simple Sliding Window

class Solution:
    def countGoodSubstrings(self, s: str) -> int:
        if len(s) < 3:
            return 0
      
        count = 0
        # Check each substring of length 3
        for i in range(len(s) - 2):
            # Get substring of exactly 3 characters
            substring = s[i:i+3]
            # Check if all characters are unique
            if len(set(substring)) == 3:
                count += 1
      
        return count

Approach 2: Optimized with Character Tracking

class Solution:
    def countGoodSubstrings(self, s: str) -> int:
        if len(s) < 3:
            return 0
      
        count = 0
        # Check each consecutive triplet
        for i in range(len(s) - 2):
            # Check if all three characters are different
            if s[i] != s[i+1] and s[i+1] != s[i+2] and s[i] != s[i+2]:
                count += 1
      
        return count

The key insight is that for "good substrings of length exactly 3", we need to check each consecutive triplet individually, not maintain a variable-size window of unique characters.