1358. Number of Substrings Containing All Three Characters

Time: O(n)

Space: O(1)

Intuition

Count substrings containing all three characters a, b, c. Sliding window: for each right pointer, track leftmost valid left. Count = l+1.

Algorithm

1Window [l,r]. Expand r. Shrink l while window has all three chars.
2For each r: number of valid subarrays ending at r = l (since any starting point 0..l-1 with r also works).

Common Pitfalls

•Count subarrays where minimum of a,b,c counts is >= 1. Answer accumulates l at each step.

1358.cs

// Approach: Sliding window; shrink left while all three characters are present; every valid window contributes 'l' substrings for each right position.
// Time: O(n) Space: O(1)

public class Solution
{
    public int NumberOfSubstrings(string s)
    {
        int ans = 0;
        int[] count = new int[3];

        int l = 0;
        foreach (char c in s)
        {
            ++count[c - 'a'];
            while (count[0] > 0 && count[1] > 0 && count[2] > 0)
                --count[s[l++] - 'a'];
            // s[0..r], s[1..r], ..., s[l - 1..r] are satisfied strings.
            ans += l;
        }

        return ans;
    }
}

Was this solution helpful?