algoadvance

You are given a string s consisting of lowercase English letters. A substring is a contiguous sequence of characters within the string. We want to count the number of substrings of size three with distinct characters.

Example:

• Input: s = "xyzzaz"
• Output: 1
• Explanation: The only valid substring is “xyz”.

Example:

• Input: s = "aababcabc"
• Output: 4
• Explanation: Valid substrings are “abc”, “bca”, “cab”, and “abc”.

Clarifying Questions

1. Input Length: What is the maximum length of the input string s?
2. Character Set: Are the characters only lowercase English letters?
3. Edge Cases: What should be the output if the string length is less than 3?

Strategy

1. Iterate through Substrings: Loop through the string and extract substrings of length 3.
2. Check Distinct Characters: For each substring, check if all characters are distinct.
3. Count Valid Substrings: Maintain a count of substrings that meet the criteria.

Implementation Steps

1. Initialize a counter to 0.
2. Use a loop to extract substrings of length 3 starting from each index except the last two.
3. Use a set to check if all characters in the substring are unique.
4. Increment the counter if the characters are unique.
5. Return the counter.

Code

Here’s how you can implement the solution in Python:

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

Time Complexity

• The loop runs n - 2 times (where n is the length of the string), and on each iteration, creating the substring and checking its characters for uniqueness takes a constant time (since we are handling substrings of a fixed length, 3).
• Overall Time Complexity: O(n), where n is the length of the string s.

This approach ensures that we efficiently count the number of valid substrings of length 3 with distinct characters.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?