Number of Substrings Containing All Three Characters

LeetCode 1460 | Difficulty: Medium

Medium

Problem Description

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.

Example 1:

Input: s = "abcabc"
Output: 10
Explanation: The substrings containing at least one occurrence of the characters a, b and c are "abc", "abca", "abcab", "abcabc", "bca", "bcab", "bcabc", "cab", "cabc" and "abc" (again).

Example 2:

Input: s = "aaacb"
Output: 3
Explanation: The substrings containing at least one occurrence of the characters a, b and c are "aaacb", "aacb" and "acb".

Example 3:

Input: s = "abc"
Output: 1

Constraints:

- `3 <= s.length <= 5 x 10^4`

- `s` only consists of *a*, *b* or *c *characters.

Topics: Hash Table, String, Sliding Window

---

Approach

Sliding Window

Maintain a window [left, right] over the array/string. Expand right to include new elements, and shrink left when the window violates constraints. Track the optimal answer as the window slides.

When to use

Finding subarrays/substrings with a property (max length, min length, exact count).

Hash Map

Use a hash map for O(1) average lookups. Store seen values, frequencies, or indices. The key question: what should I store as key, and what as value?

When to use

Need fast lookups, counting frequencies, finding complements/pairs.

---

Solutions

Solution 1: C# (Best: 60 ms)

Metric	Value
Runtime	60 ms
Memory	40.9 MB
Date	2022-02-08

Solution

public class Solution {
    public int NumberOfSubstrings(string s) {
        int[] last = new int[] {-1, -1 , -1};
    int result = 0;
    for (int i = 0; i < s.Length; i++)
    {
        last[s[i]-'a'] = i;
        if(last[0] == -1 || last[1]== -1 || last[2] == -1)
        continue;
        
        result += 1 + Math.Min(last[2], Math.Min(last[0], last[1]));        
    }
    return result;

    }
}

---

Complexity Analysis

Approach	Time	Space
Sliding Window	$O(n)$	$O(k)$
Hash Map	$O(n)$	$O(n)$

---

Interview Tips

Key Points

• Discuss the brute force approach first, then optimize. Explain your thought process.
• Clarify what makes a window "valid" and what triggers expansion vs shrinking.
• Hash map gives O(1) lookup — think about what to use as key vs value.
• LeetCode provides 2 hint(s) for this problem — try solving without them first.

💡 Hints

Hint 1: For each position we simply need to find the first occurrence of a/b/c on or after this position.

Hint 2: So we can pre-compute three link-list of indices of each a, b, and c.