We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Substrings of Size Three with Distinct Characters

Difficulty: Easy

Problem Description

Given a string s, return the number of good substrings of length three in s. A substring is considered good if it contains no repeated characters.

Key Insights

  • A substring of length 3 can only be good if all characters are distinct.
  • Use a sliding window approach to efficiently check each substring of length 3.
  • Hash sets or arrays can help track character occurrences within the window for quick validation.

Space and Time Complexity

Time Complexity: O(n) - where n is the length of the string, as we are iterating through it once. Space Complexity: O(1) - since we are only using a fixed amount of space for character tracking (26 lowercase letters).

Solution

To solve the problem, we can use a sliding window of size 3 to traverse the string. For each window, we check if all characters are distinct:

  1. Initialize a counter for good substrings.
  2. For each character in the string, check the current window of three characters.
  3. Use a set or array to track characters and ensure no duplicates.
  4. If the window contains distinct characters, increment the counter.

This approach effectively counts good substrings in a single pass through the string.

Code Solutions

def countGoodSubstrings(s: str) -> int:
    count = 0  # Initialize count of good substrings
    n = len(s)
    
    # Iterate through the string, stopping 3 characters from the end
    for i in range(n - 2):
        substring = s[i:i + 3]  # Get the substring of length 3
        if len(set(substring)) == 3:  # Check if characters are distinct
            count += 1  # Increment count if good
        
    return count  # Return the total count
← Back to All Questions