Go step by step: try it yourself before the video and the visual. Progress saves on this device.
0 / 130 pointsSolved (Medium) 0/40Reviews 0/50Mastered 0/25Practice steps 0/15
Step 1
Know these before you start
Practise each one here, or tick what you already know
Concept videoWatch the concept video if the pattern is new to you.
Step 2
Try it on paper
5–10 minutes, no code yet
ProblemProblem statementYou are given a string s consisting only of the characters 'a', 'b', and 'c'.ReadHide
Problem Statement
You are given a string s consisting only of the characters 'a', 'b', and 'c'.
A string is called valid if it does not contain "abc" as a substring.
Return the number of valid substrings in s. Substrings with different starting or ending indices are counted separately.
Added 2026-11-08 from Srujan's LeetCode Recent AC list (photo) — not previously in the repo.
Input / Output
Input: s = "abac"
Output: 10
Explanation: No "abc" appears anywhere, so all 4*5/2 = 10 substrings count.
Input: s = "abc"
Output: 5
Explanation: Only the whole string "abc" itself is invalid; the other 5 count.
Input: s = "ac"
Output: 3
Explanation: All substrings are valid.
Code it on LeetCode
There's no editor for this one here yet, so solve it on LeetCode, with its own tests. Then tick My code passed below, and it joins your reviews. With your LeetCode account linked, that happens on its own.
Solve on LeetCode An error or a Wrong Answer there? What each one means.
Step 6
Get it accepted
All test cases pass
Step 7
Review it so it sticks
Re-solve from memory after
The step that matters most: without reviews most of a solved problem fades within weeks. Three short re-solves, each just as you start to forget, are what make it yours.
Your notes
Three lines in your own words. They come back with this problem's reviews, so you can check yourself after recalling the solution.
Solve it yourself before you look
Reading the solution first feels like progress, but it makes the next similar problem — and the interview version — much harder, because you skipped the part where you figure it out. Give it an honest 20–30 minutes. Stuck? Re-read the pattern, watch the concept video, or try the brute force first.
Hidden: approach · solution code
Approach
Pattern Recognition
Last bad position — the only way a substring becomes invalid is by containing "abc", and "abc" can only end at one place: the moment we see s[r-2..r] == "abc". So for substrings ending at r, the earliest allowed start is just after the most recent "abc" that ends at or before r. Everything from that start to r is valid, and we add them all in one step — the same "count substrings ending here" trick as counting substrings without repeating characters.
Approach
Brute Force — Check Every Substring, O(n^2)
count = 0
for start in range(n):
for end in range(start, n):
if s[end-2..end] == "abc": break # longer ones are invalid too
count += 1
return count
Once "abc" shows up inside a substring, every longer substring starting at the same place is invalid as well, so the inner loop can stop early. Still quadratic in the worst case (e.g. "aaaa..." has no "abc" at all).
Optimized — Sliding Left Boundary, O(n)
left = 0
ans = 0
for r in range(len(s)):
if r >= 2 and s[r-2:r+1] == "abc":
left = max(left, r - 1) # substrings ending at r must start after r-2
ans += r - left + 1 # every start from left..r is valid
return ans
left only moves forward, and each character is visited once.
Complexity
| Approach | Time | Space | Notes |
|---|---|---|---|
| Check every substring | O(n^2) | O(1) | Early break once "abc" appears |
| Sliding left boundary | O(n) | O(1) | "abc" can only end at the current index |
Solution code
class SolutionBruteForce:
"""O(n^2) time | O(1) space — check every substring, stop early at "abc"."""
def countValidSubstrings(self, s: str) -> int:
n = len(s)
count = 0
for start in range(n):
for end in range(start, n):
if end - start >= 2 and s[end - 2:end + 1] == "abc":
break
count += 1
return count
class Solution:
"""O(n) time | O(1) space — sliding left boundary past the last "abc"."""
def countValidSubstrings(self, s: str) -> int:
ans = 0
left = 0
for r in range(len(s)):
if r >= 2 and s[r - 2:r + 1] == "abc":
left = max(left, r - 1)
ans += r - left + 1
return ansOther ways to solve it
- Community solutions on LeetCode ↗ for many more versions, in many languages. Read them after you've solved it.
Revising this one?
- →Solve it from memory before peeking
- →Say the pattern out loud, not just the code
- →Explain it like you would to a friend
- →Try it again in a different language