NeetCode #242LC-1358MediumSliding Window
← Back to All Problems#242 · #1358 · Number of Substrings Containing All Three Characters(包含所有三种字符的子字符串数目)
📌 Problem Statement & Constraints
Given a string
s consisting only of the characters a, b and c, return the number of substrings containing at least one occurrence of each of the three characters. Constraints: 3 <= s.length <= 5 * 10^4.💡 Core Algorithmic Approaches
- Maintain a window that always contains at least one of each character by shrinking from the left whenever it is complete.
- For each right endpoint, after shrinking to the minimal complete window
[l, r], every start index from 0 tol - 1yields a valid substring ending atr. - So add
lto the answer for each right endpoint. - Each pointer moves monotonically, giving O(n) overall.
💻 Benchmark Python3 Implementation
class Solution:
def numberOfSubstrings(self, s: str) -> int:
cnt = [0, 0, 0]
l = 0
res = 0
for r, ch in enumerate(s):
cnt[ord(ch) - 97] += 1
while all(c > 0 for c in cnt): # window contains all three
cnt[ord(s[l]) - 97] -= 1
l += 1
# every start in [0, l-1] yields a valid substring ending at r
res += l
return res⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n): each pointer moves monotonically; the all(...) check is over three counters.
💾 Space Complexity
O(1): a length-3 counter array.
⚠️ Interview Pitfalls & Follow-ups
- Counting only the minimal window: the number of valid substrings ending at
risl, not 1. - Shrinking before checking completeness: the shrink must happen while the window is complete, and the answer accumulates
lafter shrinking. - Using a set to check completeness: a counter is needed because the window may contain multiple copies of a character, and the shrink must not remove the last one prematurely.
- Forgetting the modulo in the character-to-index mapping:
ord(ch) - ord('a')gives 0, 1, 2 for a, b, c.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🧩 Related Sliding Window Problems
#219 · #219Contains Duplicate II#220 · #121Best Time to Buy and Sell Stock#221 · #2379Minimum Recolors to Get K Consecutive Black Blocks#222 · #1984Minimum Difference Between Highest and Lowest of K Scores#223 · #1343Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold#224 · #1052Grumpy Bookstore Owner