Number of Substrings Containing All Three Characters Solution
Number of Substrings Containing All Three Characters solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Number of Substrings Containing All Three Characters is a medium coding problem on strings, hash table and sliding window, asked in Amazon, Google and Oracle interviews.
- Difficulty: Medium
- Topics: Strings, Hash Table, Sliding Window
- Asked at: Amazon, Google, Oracle
- 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
s consists only of the characters 'a', 'b' and 'c'.
Return the number of substrings that contain at least one of each.
Example 1
Input: s = "abcabc"
Output: 10
Explanation: Every substring of length 3 or more here qualifies.
Example 2
Input: s = "aaacb"
Output: 3
Explanation: "aaacb", "aacb" and "acb".
Example 3
Input: s = "abc"
Output: 1
Constraints
3 <= s.length <= 50000s consists only of 'a', 'b' and 'c'.
Hints for Number of Substrings Containing All Three Characters
Hint 1
Fix the right end and ask how many left ends make the substring valid.
Hint 2
A substring ending at
iis valid exactly when it starts at or before the last occurrence of each character.Hint 3
So the count for right end
iismin(lastA, lastB, lastC) + 1.
How to solve Number of Substrings Containing All Three Characters
For each right end, the valid left ends form a prefix: the substring must reach back far enough to pick up all three characters, and the binding constraint is the most recent occurrence of the rarest one.
Approach
- Track
last[c], the most recent index of each of the three characters, all starting at-1. - At index
i, updatelast[s[i]]. - Add
min(last) + 1to the total — the number of valid starts.
Why it works
A substring [l, i] holds all three characters precisely when l <= last[c] for every c, because last[c] is the rightmost occurrence at or before i. The number of such l is min(last) + 1, and it is 0 while some character has not appeared, since min is then -1.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- The equivalent two-pointer formulation counts
lrather thann - r, which is easy to get off by one. - Initialising
lastto 0 instead of-1counts substrings before all three characters exist. - The total reaches about
1.25 · 10^9at the upper limit, right at the edge ofint.
Reference solution
Python
def numberOfSubstrings(s: str) -> int:
last = [-1, -1, -1]
total = 0
for i, ch in enumerate(s):
last[ord(ch) - 97] = i
total += min(last) + 1
return totalJava
public static int numberOfSubstrings(String s) {
int[] last = { -1, -1, -1 };
int total = 0;
for (int i = 0; i < s.length(); i++) {
last[s.charAt(i) - 'a'] = i;
total += Math.min(last[0], Math.min(last[1], last[2])) + 1;
}
return total;
}C++
int numberOfSubstrings(string s) {
int last[3] = { -1, -1, -1 };
int total = 0;
for (int i = 0; i < (int) s.size(); i++) {
last[s[i] - 'a'] = i;
total += min(last[0], min(last[1], last[2])) + 1;
}
return total;
}JavaScript
var numberOfSubstrings = function(s) {
var last = [-1, -1, -1];
var total = 0;
for (var i = 0; i < s.length; i++) {
last[s.charCodeAt(i) - 97] = i;
total += Math.min(last[0], last[1], last[2]) + 1;
}
return total;
};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