Check if All A's Appears Before All B's
easyTime: O(n)Space: O(1)
The shape of the problem
Given a string of only `a` and `b`, return true iff every `a` comes before every `b`. Equivalent to: the string is `a…ab…b` with either side possibly empty.
Signals to notice
single character scanmonotonic stateno backtracking
Brute force first
For every `a`, check that no `b` appears before it. O(n²) and does a lot of repeat work.
The key insight
The answer is false iff there is an "ba" substring anywhere. Detecting that is a one-pass state-machine with two states: "still in a-zone" → "in b-zone".
Trace it on s="aaabbb"
i=0 "a" seenB=false i=1 "a" seenB=false i=2 "a" seenB=false i=3 "b" seenB=true i=4 "b" seenB=true i=5 "b" seenB=true → end → return true
What must stay true
Before the first `b`, every character seen is `a`. After the first `b`, every character seen must be `b`.
Shape of the loop
seenB = false for c in s: if c == "b": seenB = true elif seenB: return false # an "a" after a "b" return true
Pseudocode only — the full worked solution lives in the Solution tab.
Easy way to go wrong
Checking `if s[i]=="a" and s[i-1]=="b"` only once per index but forgetting the edge case where the string is entirely `a`s or entirely `b`s (both return true).