Substrings of Size Three with Distinct Characters - Video Solutions

Problem Overview: Given a string s, count how many substrings of length three contain all distinct characters. Each valid substring must have three different characters, meaning no duplicates inside the window.

Approach 1: Naive Enumeration (Time: O(n), Space: O(1))

The direct way is to examine every substring of length three. Iterate through the string from index 0 to n-3, extract the three characters at i, i+1, and i+2, and check whether they are all different. A simple comparison such as a != b, a != c, and b != c verifies uniqueness. Each iteration performs constant work, so the overall time complexity is O(n) and space complexity is O(1). This approach works because the substring length is fixed at three, eliminating the need for dynamic structures like a hash table. It is straightforward and often the quickest implementation during interviews when constraints are small.

Approach 2: Sliding Window Technique (Time: O(n), Space: O(1))

A more general solution uses the sliding window pattern. Maintain a window of size three that moves from left to right across the string. For each window, track character frequencies using a small counter array or map. When the window reaches size three, check whether all counts are 1. If so, the substring contains distinct characters and contributes to the answer. Then slide the window forward by removing the leftmost character and adding the next one on the right.

This method demonstrates a reusable pattern for substring problems. Instead of recomputing uniqueness from scratch, the window updates counts incrementally as it moves. Each character enters and leaves the window at most once, producing linear time complexity O(n). Space usage stays O(1) because the alphabet size is bounded. Problems involving substring counting frequently combine string traversal with frequency tracking and incremental updates.

The sliding window approach becomes especially valuable when the substring size is not fixed or when you must track additional conditions like character frequency limits. It also scales naturally to larger windows or variable-length substring constraints.

Recommended for interviews: The sliding window approach is what interviewers typically expect. The naive method proves you understand the problem and edge cases, but sliding window shows familiarity with a core string-processing pattern. Demonstrating the ability to maintain counts while shifting the window signals strong algorithmic fundamentals.