#1358
Medium Algorithms Number of substrings containing all three characters
Hash Table String Sliding Window
73.5% acceptance
Feb 25, 2026
4403
81
Given a string s consisting only of characters a, b and c.
Return the number of substrings containing at least one occurrence of all these characters a, b and c.
Solution
Rust
Time O(n)
Space O(1)
impl Solution {
pub fn number_of_substrings(s: String) -> i32 {
let s = s.as_bytes();
let n = s.len();
let mut last = [-1i32; 3]; // last seen index of 'a','b','c'
let mut count = 0i32;
for i in 0..n {
last[(s[i] - b'a') as usize] = i as i32;
let min_last = *last.iter().min().unwrap();
count += min_last + 1;
}
count
}
}