Skip to main content
Talentd

Substrings of Size Three with Distinct Characters - Solution & Explanation

EasyHash TableStringSliding WindowCounting17 min readAsked at: Amazon, Microsoft, Visa +2
Practice this problem

Problem Statement

A string is good if there are no repeated characters.

Given a string s​​​​​, return the number of good substrings of length three in s​​​​​​.

Note that if there are multiple occurrences of the same substring, every occurrence should be counted.

A substring is a contiguous sequence of characters in a string.

 

Example 1:

Input: s = "xyzzaz"
Output: 1
Explanation: There are 4 substrings of size 3: "xyz", "yzz", "zza", and "zaz". 
The only good substring of length 3 is "xyz".

Example 2:

Input: s = "aababcabc"
Output: 4
Explanation: There are 7 substrings of size 3: "aab", "aba", "bab", "abc", "bca", "cab", and "abc".
The good substrings are "abc", "bca", "cab", and "abc".

 

Constraints:

  • 1 <= s.length <= 100
  • s​​​​​​ consists of lowercase English letters.

Approach Overview

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.

Approach 1: Naive Approach

This approach involves iterating over the string and extracting all possible substrings of length three. For each substring, we check if it contains all unique characters by employing a set, as sets do not allow duplicate entries.

The C solution defines a helper function isUnique to check if a substring of length three is good (i.e., all characters are unique). It iteratively checks each substring and increments the count for good substrings.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), where n is the length of the string.
Space Complexity: O(1), as no extra data structures are used beyond a few variables.

Try this approach in the editor →

Approach 2: Sliding Window Technique

This efficient approach uses the sliding window technique to iterate over possible substrings of length three. The sliding window maintains the state of the current substring and checks for uniqueness in constant time as it slides over the string.

The C code uses a simple loop to check the condition on each group of three consecutive characters, utilizing a helper function for clarity within the loop.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), where n is the length of the string.
Space Complexity: O(1), with a constant amount of space used for variables.

Try this approach in the editor →

Approach 3: Sliding Window

We can maintain a sliding window such that the characters within the window are not repeated. Initially, we use a binary integer mask of length 26 to represent the characters within the window, where the i-th bit being 1 indicates that character i has appeared in the window, otherwise it indicates that character i has not appeared in the window.

Then, we traverse the string s. For each position r, if s[r] has appeared in the window, we need to move the left boundary l of the window to the right until there are no repeated characters in the window. After this, we add s[r] to the window. At this point, if the length of the window is greater than or equal to 3, then we have found a good substring of length 3 ending at s[r].

After the traversal, we have found the number of all good substrings.

The time complexity is O(n), where n is the length of the string s. The space complexity is O(1).

This solution can be extended to find the number of good substrings of length k.

Code

PythonJavaC++GoTypeScriptPHP

Python

Java

C++

Go

TypeScript

PHP

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Naive Approach

Time Complexity: O(n), where n is the length of the string.
Space Complexity: O(1), as no extra data structures are used beyond a few variables.

Sliding Window Technique

Time Complexity: O(n), where n is the length of the string.
Space Complexity: O(1), with a constant amount of space used for variables.

Sliding Window—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Naive EnumerationO(n)O(1)Quick implementation when substring size is fixed and small
Sliding Window TechniqueO(n)O(1)Preferred interview approach; scalable to variable window problems

Video Solution

Substrings of Size Three with Distinct Characters | Sliding Window • Shiva Prasad Gurram • 2,214 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Substrings of Size Three with Distinct Characters easy or hard?
Substrings of Size Three with Distinct Characters is classified as an Easy problem. The logic is straightforward because the substring length is fixed at three. The challenge mainly involves recognizing that a sliding window pattern can generalize the solution.
Substrings of Size Three with Distinct Characters Python/Java solution
In Python or Java, iterate through the string while maintaining a window of length three. Check if the three characters are distinct using comparisons or a small set. The sliding window version updates character counts as the window moves and maintains O(n) time complexity.
How to solve Substrings of Size Three with Distinct Characters in O(n)?
Iterate through the string using a sliding window of length three. Track the characters currently inside the window using a small frequency map or array. If the window contains three unique characters, increment the count. Slide the window forward by removing the left character and adding the next character on the right.
What is the best approach for Substrings of Size Three with Distinct Characters?
The sliding window technique is the preferred approach. Maintain a window of size three and track character frequencies as the window moves across the string. Each step checks whether all characters in the window are unique. This runs in O(n) time and O(1) space and demonstrates a common pattern used in many substring problems.
Is Substrings of Size Three with Distinct Characters asked at Google/Amazon/Meta?
Substring counting problems using sliding window techniques appear frequently in interviews at companies like Google, Amazon, and Meta. While this exact problem may vary, the underlying pattern of maintaining a fixed-size window and tracking character frequencies is commonly tested.
What data structure is used in Substrings of Size Three with Distinct Characters?
Most solutions rely on simple character comparisons or a small frequency structure such as an array or hash map. When using the sliding window technique, a frequency array or hash table tracks how many times each character appears inside the current window.
What is the time complexity of Substrings of Size Three with Distinct Characters?
The optimal time complexity is O(n), where n is the length of the string. Each character is processed at most once as the window slides through the string. Space complexity remains O(1) because the algorithm only stores counts for a small fixed alphabet.

Ready to solve this problem?

Practice Substrings of Size Three with Distinct Characters with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Longest Substring Without Repeating Characters