1358. Number of Substrings Containing All Three Characters

Hash Table
String
Sliding Window

TIME

O(n)

SPACE

O(1)

Intuition

Count valid substrings by their right endpoint. A substring ending at index i contains all three characters iff its start is at or before the most recent position where the rarest-so-far of the three was last seen. Concretely, if last[a], last[b], last[c] are the most recent indices of each character up to i, then any start j with 0 <= j <= min(last[a], last[b], last[c]) yields a valid substring.

Approach

Keep last = [-1, -1, -1] for the last seen index of a, b, c.
Sweep i over s, updating last[s[i]].
If all three are >= 0, every start 0..min(last) works, so add min(last) + 1 to the answer.

Complexity

Time: O(n)
Space: O(1)

Edge Cases

Before all three have appeared → min(last) = -1 contributes 0
All same character → never valid → 0 (though constraints guarantee length ≥ 3, content can still lack a letter)
Answer can reach ~n²/2 (≈ 1.25 * 10^9) → fits in a 64-bit int; use long in Java

Code

class Solution:
    def numberOfSubstrings(self, s: str) -> int:
        """
        1358. Number of Substrings Containing All Three Characters
        Time: O(n)
        Space: O(1)
        """
        last = [-1, -1, -1]  # last index of a, b, c
        ans = 0
        for i, ch in enumerate(s):
            last[ord(ch) - ord("a")] = i
            ans += min(last) + 1  # min(last) = -1 until all three seen
        return ans

/**
 * 1358. Number of Substrings Containing All Three Characters
 * Time: O(n)
 * Space: O(1)
 */
class Solution {
    public int numberOfSubstrings(String s) {
        int[] last = {-1, -1, -1}; // last index of a, b, c
        int ans = 0;
        for (int i = 0; i < s.length(); i++) {
            last[s.charAt(i) - 'a'] = i;
            int m = Math.min(last[0], Math.min(last[1], last[2]));
            ans += m + 1; // m = -1 until all three seen
        }
        return ans;
    }
}