Check if All A's Appears Before All B's

Start by scanning the string to detect if any 'b' occurs before an 'a'. If a 'b' precedes an 'a', the condition fails and we return false. Otherwise, every 'a' appears before all 'b's, and we return true. This approach leverages a linear pass and is efficient for strings with only 'a' and 'b'.

Problem Statement

You are given a string s containing only the characters 'a' and 'b'. Return true if every 'a' occurs before any 'b' in s, otherwise return false. The goal is to verify the strict ordering of characters using a straightforward string-driven approach.

For example, in s = "aaabbb", all 'a's are before 'b's, so the result is true. In s = "abab", there is an 'a' after a 'b', so the result is false. Consider edge cases like strings with only 'b's or only 'a's to fully validate your solution.

Examples

Example 1

Input: s = "aaabbb"

Output: true

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

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

There are no 'a's, hence, every 'a' appears before every 'b' and we return true.

Constraints

• 1 <= s.length <= 100
• s[i] is either 'a' or 'b'.

Solution Approach

Single Pass Detection

Iterate through the string from start to end. Track whether a 'b' has been seen. If you encounter an 'a' after a 'b', immediately return false. Otherwise, finish the iteration and return true.

Using Index Comparison

Find the last index of 'a' and the first index of 'b'. If the last 'a' index is less than the first 'b' index, return true. This provides a direct check without scanning every character individually.

Boolean Flag Approach

Maintain a boolean flag indicating if any 'b' has appeared. For each character, update the flag and check if an 'a' comes after a 'b'. This approach ensures linear time complexity and simple state tracking.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) since the string is scanned once, and space complexity is O(1) because only a few variables are needed to track the state.

What Interviewers Usually Probe

• They may hint at checking 'b' before 'a' as an opposite strategy.
• Expect candidates to recognize linear scan suffices due to the two-character constraint.
• Look for proper handling of edge cases like all 'a's or all 'b's.

Common Pitfalls or Variants

Common pitfalls

• Assuming characters other than 'a' and 'b' can appear.
• Failing to handle strings with no 'a's or no 'b's.
• Overcomplicating with extra data structures instead of a simple pass.

Follow-up variants

• Check if all 'b's appear after all 'c's in a similar character-constrained string.
• Determine if a string of 'x' and 'y' follows a strict order like 'x' before 'y'.
• Validate sequences where multiple character types must appear in defined order.

FAQ

How can I quickly check if all 'a's appear before all 'b's?

Use a single pass through the string, marking if a 'b' appears and return false if an 'a' occurs afterward.

Does this problem require extra memory for tracking positions?

No, you only need a boolean flag or indices to track last 'a' and first 'b', keeping space O(1).

What should I return for strings with only 'b's or only 'a's?

Always return true since there are no violations of 'a' before 'b' ordering.

Can I use built-in string functions to solve this?

Yes, functions like indexOf and lastIndexOf can simplify checks without scanning every character manually.

What pattern does this problem follow in interviews?

It follows a string-driven solution pattern where order detection and early termination prevent unnecessary computation.