Substrings of Size Three with Distinct Characters — Solution
Substrings of Size Three with Distinct Characters solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Substrings of Size Three with Distinct Characters is an easy coding problem on strings, hash table and counting, asked in Amazon, Adobe and Cognizant interviews.
- Difficulty: Easy
- Topics: Strings, Hash Table, Counting, Sliding Window
- Asked at: Amazon, Adobe, Cognizant
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A string is good when it has no repeated characters.
Return the number of good substrings of length exactly three in s. Substrings that occur more than once are counted each time.
Example 1
Input: s = "codekairo"
Output: 7
Explanation: Every window of three is good: cod, ode, dek, eka, kai, air, iro.
Example 2
Input: s = "xyzzaz"
Output: 1
Explanation: Only "xyz" has three distinct characters.
Example 3
Input: s = "aababcabc"
Output: 4
Explanation: "abc", "bca", "cab" and "abc" again.
Constraints
1 <= s.length <= 100000s consists of lowercase English letters.
Hints for Substrings of Size Three with Distinct Characters
Hint 1
The window is fixed at three characters, so there are at most
n - 2of them.Hint 2
Three characters are distinct exactly when all three pairwise comparisons differ.
Hint 3
No tally is needed at this size — three comparisons per window is enough.
How to solve Substrings of Size Three with Distinct Characters
With a window this small, the distinctness test is three equality checks, so a direct scan over every window of length three is already linear.
Approach
- Walk
ifrom 0 whilei + 3 <= |s|. - Check
s[i] != s[i+1],s[i+1] != s[i+2]ands[i] != s[i+2]. - Count the windows that pass.
Why it works
Three values are pairwise distinct precisely when all three unordered pairs differ; checking only adjacent pairs would accept "aba". Each window costs constant time, so the whole scan is O(n).
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- Comparing only neighbouring characters wrongly accepts patterns like
"aba". - A string shorter than three characters has no windows and the answer is 0.
- Repeated occurrences of the same substring each count — this is not a distinct-substring count.
Reference solution
Python
def countGoodSubstrings(s: str) -> int:
count = 0
for i in range(len(s) - 2):
if s[i] != s[i + 1] and s[i + 1] != s[i + 2] and s[i] != s[i + 2]:
count += 1
return countJava
public static int countGoodSubstrings(String s) {
int count = 0;
for (int i = 0; i + 3 <= s.length(); i++) {
char a = s.charAt(i), b = s.charAt(i + 1), c = s.charAt(i + 2);
if (a != b && b != c && a != c) count++;
}
return count;
}C++
int countGoodSubstrings(string s) {
int count = 0;
for (int i = 0; i + 3 <= (int) s.size(); i++) {
if (s[i] != s[i + 1] && s[i + 1] != s[i + 2] && s[i] != s[i + 2]) count++;
}
return count;
}JavaScript
var countGoodSubstrings = function(s) {
var count = 0;
for (var i = 0; i + 3 <= s.length; i++) {
var a = s.charAt(i), b = s.charAt(i + 1), c = s.charAt(i + 2);
if (a !== b && b !== c && a !== c) count++;
}
return count;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Hashing: Hash Maps and Hash Sets