PPractick

The problem

A text-analysis tool processes strings over the letters a, b and c, and needs the number of substrings that contain at least one of each letter. Counting per right end is the key. For a substring ending at index i to contain all three letters, it must start at or before the earliest of the three letters' most recent positions. If those last-seen indices are la, lb and lc, every start from 0 to min(la, lb, lc) works, which is min + 1 substrings. One pass, three variables.

Example: "abcabc" → 10.

Function signature

long long numberOfSubstrings(const string& s);  // s consists of 'a', 'b', 'c'

Test cases

Input	Output	Explanation
"abcabc"	10
"aaacb"	3	"aaacb", "aacb", "acb"
"abc"	1
"cba"	1
"aaa"	0	b and c never appear

(Confirm: only the letters a, b and c appear; substrings are contiguous and counted by position.)

How interviewers phrase it

• "Given a string of characters a, b and c, return the number of substrings containing at least one occurrence of each" (LeetCode 1358).

Clarifying questions to ask

1. Only a, b and c? (Yes.)
2. At least one of each? (Yes.)
3. How large is n? (Up to 5·10⁴; the count can reach about n²/2, so use 64-bit.)

Follow-ups to expect

1. "Why min(last) + 1?"
2. "Sliding-window version?"
3. "Complement approach?"
4. "Generalise to k required letters?"
5. "Complexity?"

Related questions

• Longest Repeating Character Replacement Hard
• Longest Substring With At Most K Distinct Characters Hard
• Minimum Window Substring Hard
• Minimum Window Subsequence Hard
• Count Number of Substrings Easy
• Longest Substring Without Repeating Characters Medium

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in