Check if All A's Appears Before All B's - Video Solutions

Problem Overview: Given a string containing only characters 'a' and 'b', verify that every 'a' appears before any 'b'. The moment an 'a' appears after a 'b', the rule is violated and the result should be false.

Approach 1: One-Pass Iteration Using a Flag (O(n) time, O(1) space)

The simplest solution scans the string once from left to right. Maintain a boolean flag that records whether a 'b' has already appeared. While iterating, if you see 'b', set the flag. If you later encounter 'a' while the flag is already set, the order constraint is broken and you return false. If the scan finishes without this violation, the string satisfies the requirement.

This approach works because the condition only depends on relative order, not positions or counts. A single pass over the string is enough to detect the first invalid pattern. It avoids extra data structures and keeps memory usage constant. This is the typical solution used in interviews because it is straightforward and optimal.

Approach 2: Using Regex Match (O(n) time, O(1) space)

A pattern-based solution uses a regular expression that matches valid strings. The only valid form is zero or more 'a' characters followed by zero or more 'b' characters. The regex pattern ^a*b*$ enforces exactly that structure.

Run a full string match using this pattern. If the match succeeds, all 'a' characters appear before all 'b' characters. If it fails, there must be a substring like "ba" that violates the ordering rule. Modern regex engines process this pattern in linear time for this case, so the time complexity remains O(n).

This approach relies on the language’s regex engine instead of manual iteration. It produces very compact code but hides the actual logic behind the pattern. In coding interviews, this method may be acceptable but interviewers usually prefer seeing the explicit algorithm.

Recommended for interviews: The one-pass flag approach is the expected solution. It demonstrates clear reasoning about ordering constraints and uses constant space with O(n) time. The regex solution is concise but less explicit, so it is better suited for quick scripting rather than explaining your thought process during interviews.