Substrings of Size Three with Distinct Characters

Substrings of Size Three with Distinct Characters

What is this problem about?

This "Easy" level challenge focuses on identifying specific patterns within a string. Given a string, you need to count how many substrings of exactly length three consist of three unique characters. For example, in the string "abacaba", the substring "bac" is valid because 'b', 'a', and 'c' are all different, while "aba" is invalid because 'a' is repeated.

Why is this asked in interviews?

Companies like Meta, Amazon, and Visa use this question to screen for basic coding fluency and familiarity with the sliding window technique. It's a foundational problem that tests if a candidate can correctly manage loop boundaries and implement a simple character-counting mechanism. It also serves as a warm-up to more complex sliding window problems that involve dynamic sizes or larger character sets.

Algorithmic pattern used

The "Fixed-Size Sliding Window" pattern is the most efficient way to solve this. Instead of creating new substrings, you maintain a window of size three and shift it one character at a time from left to right. At each step, you check the three characters currently in the window. Since the window is very small (always three), you can use a simple set or even direct comparisons (e.g., s[i] != s[i+1] && s[i] != s[i+2] && s[i+1] != s[i+2]) to verify uniqueness.

Example explanation

Let's take the string "xyzzaz".

• First window: "xyz" -> All characters ('x', 'y', 'z') are distinct. Count = 1.
• Second window: "yzz" -> 'z' is repeated. Count remains 1.
• Third window: "zza" -> 'z' is repeated. Count remains 1.
• Fourth window: "zaz" -> 'z' is repeated. Count remains 1. Total count is 1. If the string was "abcabc", every window of size three would be "abc", "bca", "cab", etc., all of which are distinct.

Common mistakes candidates make

1. Off-by-one errors: Miscalculating the loop limit, such as iterating until i < string.length instead of i <= string.length - 3, which can lead to index out of bounds errors.
2. Using heavy data structures: While a Hash Set works, it might be overkill for just three characters. Candidates sometimes over-engineer the solution when simple comparisons are faster.
3. Ignoring small strings: Failing to return 0 immediately if the input string length is less than three.

Interview preparation tip

For any problem involving "substrings of size K," immediately think of the sliding window pattern. Practice implementing it both with a hash map (for counting frequencies) and with direct index access. Even for simple problems, writing clean, bug-free code on the first try is what interviewers look for in "Easy" questions.