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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Substrings of Size Three with Distinct Characters

Number: 1987

Difficulty: Easy

Paid? No

Companies: Accenture, Adobe, Quora

Problem Description

Given a string s, count the number of substrings of length three that have all distinct characters. A substring is a contiguous block of characters, and if there are multiple occurrences of the same substring, every occurrence is counted.

Key Insights

  • The problem involves checking every substring of fixed length (3) in the string.
  • A substring is considered "good" if all three characters are distinct.
  • The sliding window technique is optimal since the window size is fixed.
  • A simple check using a set can determine if all characters in the substring are distinct.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the string. We traverse the string once. Space Complexity: O(1), since the fixed-size substring (set of at most 3 characters) uses constant space.

Solution

We use the sliding window approach to consider every contiguous substring of length 3. For each window, we convert the substring to a set and check if its size is 3, meaning all characters are unique. We then increment a counter for each valid substring. This approach is efficient due to the fixed window size and minimal operations for each window.

Code Solutions

# Function to count good substrings with distinct characters
def countGoodSubstrings(s: str) -> int:
    count = 0
    # Traverse the string with a window of length 3
    for i in range(len(s) - 2):
        # Get the current substring of length 3
        substring = s[i:i+3]
        # If all characters are distinct, then the set of characters will have length 3
        if len(set(substring)) == 3:
            count += 1
    return count

# Test code
if __name__ == "__main__":
    test_string = "aababcabc"
    print(countGoodSubstrings(test_string))
← Back to All Questions