algoadvance

Leetcode 1876. Substrings of Size Three with Distinct Characters

Problem Statement

You are given a string s of length n. Your task is to find the number of substrings of length 3 that consist of distinct characters.

Example 1:

Input: s = "xyzzaz"
Output: 1
Explanation: There is only one substring of size 3 with distinct characters: "xyz".

Example 2:

Input: s = "aababcabc"
Output: 4
Explanation: Substrings with 3 unique characters are "abc", "bca", "cab" and "abc".

Clarifying Questions

1. Input Constraints:
   • Can the string contain non-alphabet characters? (It’s implied to be alphabetic based on example)
   • What is the maximum length n of the input string?
2. Output:
   • Is the function expected to only print the result or return it?

Strategy

1. Sliding Window Approach:
   • Use a sliding window of size 3 to traverse the string.
   • At each step, check if the characters in the current window are distinct.
   • Count such valid windows.
2. Distinct Check:
   • Use a set to check if the characters in the current substring are unique.

Code

#include <iostream>
#include <unordered_set>

int countGoodSubstrings(std::string s) {
    if (s.length() < 3) return 0;
    
    int count = 0;
    
    for (int i = 0; i <= s.length() - 3; ++i) {
        std::unordered_set<char> unique_chars(s.begin() + i, s.begin() + i + 3);
        if (unique_chars.size() == 3) {
            ++count;
        }
    }
    
    return count;
}

int main() {
    // Test cases
    std::string s1 = "xyzzaz";
    std::string s2 = "aababcabc";
    
    std::cout << "Count for s1: " << countGoodSubstrings(s1) << std::endl;
    std::cout << "Count for s2: " << countGoodSubstrings(s2) << std::endl;
    
    return 0;
}

Explanation of the Code

1. Initial Checks: If the string length is less than 3, return 0 because no substring of size 3 is possible.

2. Sliding Window Loop: Iterate through the string from the start to length - 3. For each iteration:
   • Construct a set containing the characters of the current substring of length 3.
   • If the size of the set is 3, that means all characters are unique, so increment the count.
3. Return the Count: Finally, return the count of valid substrings.

Time Complexity

• Time Complexity: O(n), where n is the length of the string. We are iterating through the string once and performing a fixed amount of work (3 insertions into a set) at each step.
• Space Complexity: O(1), since the set contains at most 3 characters.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• 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?