Substrings Holding a, b and c
MediumSliding Window
Problem
A string s uses only the letters a, b and c. A substring is complete if it contains at least one of each of the three letters.
Return the number of complete substrings of s. Substrings at different positions count separately.
Example 1
- Input:
- s = "aabcb"
- Output:
- 4
Complete substrings: "aabc", "aabcb", "abc", "abcb".
Example 2
- Input:
- s = "bbacb"
- Output:
- 5
Every substring that contains "bac" or "acb": "bbac", "bbacb", "bac", "bacb", "acb".
Constraints
- 1 ≤ s.length ≤ 10^5
- s contains only 'a', 'b' and 'c'.
Hint
Show the first hint
If s[l..r] is complete, then s[l'..r] is complete for every l' ≤ l.
Walkthrough
How to approach it
01Clarify before coding
- At least one of each, not exactly one? At least one.
- Are other letters possible? No, only a, b, c.
- Is the answer potentially large? Up to about n²/2 = 5·10^9, so use 64-bit integers in typed languages.
02Brute force
For every start, scan right until all three letters appear at position j; every end from j to n - 1 then works, so add n - j.
Cost: O(n²) in the worst case (a long run of one letter before the others appear).
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.