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'.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.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n) where n is the length of the string.
Space Complexity: O(1) since no additional space is used.
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.
C++
Java
Python
C#
JavaScript
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 | 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. |
Check if All A's Appears Before All B's | LeetCode 2124 | LeetCode Weekly 274 | JAVA | HINDI • Pepcoding • 1,044 views views
Watch 9 more video solutions →Practice Check if All A's Appears Before All B's with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor