⚡Flashcard Drill➔
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

  1. Maintain a window that always contains at least one of each character by shrinking from the left whenever it is complete.
  2. For each right endpoint, after shrinking to the minimal complete window [l, r], every start index from 0 to l - 1 yields a valid substring ending at r.
  3. So add l to the answer for each right endpoint.
  4. 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 r is l, not 1.
  • Shrinking before checking completeness: the shrink must happen while the window is complete, and the answer accumulates l after 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.
🎯 Drill This Card Now➔

🧩 Related Sliding Window Problems