Medium

Number of Substrings Containing All Three Characters

LAB

Given a string containing a, b, and c, return the number of substrings containing at least one of each.

EXAMPLES

Example 1

Input
{
  "s": "abcabc"
}

Output
10

FUNCTION SHAPE

s: string→int

SOLUTION NOTE

Min template (FFFTTT). Once we are valid, any subsequent substring is valid.

Key insight: res += n-r, since all subarrays that start at index l and end at some index between [r, n-1] work (because of monotonicity).

Reveal reference solution +

pythonREFERENCE

def numberOfSubstrings(self, s: str) -> int:
    freq = Counter()
    n = len(s)
    l = 0
    res = 0

    for r in range(n):
        freq[s[r]] += 1

        while len(freq) == 3:
            res += n - r  # all subarrays with end index [r, n-1] work
            freq[s[l]] -= 1
            if freq[s[l]] == 0: del freq[s[l]]
            l += 1

    return res

TimeO(n)

SpaceO(1)

Open on LeetCode ↗