Check if All A's Appears Before All B's - Solution & Explanation
Problem Statement
Given a string s consisting of only the characters 'a' and 'b', return true if every 'a' appears before every 'b' in the string. Otherwise, return false.
Example 1:
Input: s = "aaabbb" Output: true Explanation: The 'a's are at indices 0, 1, and 2, while the 'b's are at indices 3, 4, and 5. Hence, every 'a' appears before every 'b' and we return true.
Example 2:
Input: s = "abab" Output: false Explanation: There is an 'a' at index 2 and a 'b' at index 1. Hence, not every 'a' appears before every 'b' and we return false.
Example 3:
Input: s = "bbb" Output: true Explanation: There are no 'a's, hence, every 'a' appears before every 'b' and we return true.
Constraints:
1 <= s.length <= 100s[i]is either'a'or'b'.
Approach Overview
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.
Approach 1: One-Pass Iteration Using a Flag
This approach uses a single iteration through the string and a flag variable to determine if all 'a's appear before all 'b's. The flag is set when the first 'b' is encountered. If an 'a' is found after the flag is set, the function returns false. Otherwise, it returns true, as all 'a's appear before 'b's.
The function iterates through the string s. When a 'b' is found, a flag bFound is set to true. If an 'a' appears after this flag is set, the function returns false, indicating that not all 'a's appear before 'b's. Otherwise, it returns true.
Complexity
Time Complexity: O(n) where n is the length of the string.
Space Complexity: O(1) since no additional space is used.
Approach 2: Using Regex Match
An alternative approach uses regular expressions to check if the string matches a pattern of any number of 'a's followed by any number of 'b's. This can be achieved using a regex /^a*b*$/ that ensures 'a's are only followed by 'b's.
In C, regex operations require compiling the pattern and then executing it. The pattern ^a*b*$ ensures all 'a's come before any 'b's, and the string matches this pattern or not determines the outcome.
Complexity
Time Complexity: Depends on regex engine implementational overhead, but usually linear in this simple case.
Space Complexity: It involves overhead pertaining to regex structures, but generally O(1) additional space for small inputs.
Approach 3: Brain Teaser
According to the problem statement, the string s consists only of characters a and b.
To ensure that all as appear before all bs, the condition that must be met is that b should not appear before a. In other words, the substring "ba" should not be present in the string s.
The time complexity is O(n), where n is the length of the string s. The space complexity is O(1).
Complexity Comparison
| Approach | Complexity |
|---|---|
| One-Pass Iteration Using a Flag | Time Complexity: O(n) where n is the length of the string. |
| Using Regex Match | Time Complexity: Depends on regex engine implementational overhead, but usually linear in this simple case. |
| Brain Teaser | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| One-Pass Iteration Using a Flag | O(n) | O(1) | Best general solution; interview-friendly and minimal memory usage |
| Regex Pattern Match (^a*b*$) | O(n) | O(1) | Useful when regex utilities are allowed and concise code is preferred |
Video Solution
Check if All A's Appears Before All B's | LeetCode 2124 | LeetCode Weekly 274 | JAVA | HINDI • Pepcoding • 1,124 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Check if All A's Appears Before All B's easy or hard?
How to solve Check if All A's Appears Before All B's in O(n)?
Check if All A's Appears Before All B's Python or Java solution
What is the best approach for Check if All A's Appears Before All B's?
What data structure is used in Check if All A's Appears Before All B's?
What is the time complexity of Check if All A's Appears Before All B's?
Is Check if All A's Appears Before All B's asked at Google, Amazon, or Meta?
Ready to solve this problem?
Practice Check if All A's Appears Before All B's with our built-in code editor and test cases.
Practice on FleetCodeTable of Contents
Practice this problem
Open in Editor