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

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

What is this problem about?

The "Check if All A's Appears Before All B's interview question" is a string property check. You are given a string consisting only of the characters 'a' and 'b'. You need to determine if every 'a' in the string occurs before every 'b'. Effectively, this means the string should never contain the sequence "ba" as a substring.

Why is this asked in interviews?

Amazon and Microsoft ask the "Check if All A's Appears Before All B's coding problem" to test basic logical reasoning and string traversal. It evaluates whether a candidate can identify the core constraint—that once a 'b' is seen, no more 'a's are allowed. It’s an introductory "String interview pattern" problem that checks for clean, efficient logic.

Algorithmic pattern used

This problem can be solved with several patterns:

1. Substring Search: Simply check if the string contains the substring "ba". If it does, return false.
2. Flag Tracking: Maintain a boolean seen_b initially set to false. Iterate through the string. If you see 'b', set the flag. If you see 'a' while the flag is true, return false.
3. Sorting Comparison: Compare the original string with its sorted version. If they are the same, all 'a's must be at the beginning. (Note: this is $O(N \log N)$, whereas the other two are $O(N)$).

Example explanation

String: "aaabbb"

• Pass 1: No "ba" found. Result: True. String: "abab"
• index 1 is 'b', index 2 is 'a'. Sequence "ba" found. Result: False. String: "bbb"
• No 'a' seen after 'b'. Result: True.

Common mistakes candidates make

• Over-complicating: Trying to count the number of 'a's and 'b's instead of just checking their relative order.
• Incorrect "ba" check: Only checking adjacent characters when the rule applies to any 'a' appearing anywhere after a 'b'. (Wait, if any 'a' appears after any 'b', then there must be at least one adjacent "ba" somewhere in between, so the adjacent check actually is sufficient!).
• Empty strings: Not considering the case where 'a' or 'b' might be missing entirely.

Interview preparation tip

Think about the "state transition" of the problem. You start in a state where only 'a's are allowed. Once you transition to the 'b' state, you can never go back to 'a'. This mental model helps solve many similar ordering problems in "String interview pattern" tasks.