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 <= 100s consists of lowercase English letters.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.
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.
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.
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.
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.
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.
| Approach | Complexity |
|---|---|
| Naive Approach | Time Complexity: O(n), where n is the length of the string. |
| Sliding Window Technique | Time Complexity: O(n), where n is the length of the string. |
| Sliding Window | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Naive Enumeration | O(n) | O(1) | Quick implementation when substring size is fixed and small |
| Sliding Window Technique | O(n) | O(1) | Preferred interview approach; scalable to variable window problems |
Substrings of Size Three with Distinct Characters | Sliding Window • Shiva Prasad Gurram • 2,137 views views
Watch 9 more video solutions →Practice Substrings of Size Three with Distinct Characters with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor