Problem Description

You are given a string s that contains only the characters 'a' and 'b'. Your task is to determine if all 'a' characters appear before all 'b' characters in the string.

The function should return true if every 'a' in the string comes before every 'b'. If there's any 'b' that appears before an 'a', return false.

For example:

• "aaabbb" would return true because all 'a's come before all 'b's
• "abab" would return false because there's an 'a' that comes after a 'b'
• "aaa" would return true because there are only 'a's
• "bbb" would return true because there are only 'b's

The solution cleverly checks if the substring "ba" exists in the string. If "ba" is found, it means there's at least one 'b' followed by an 'a', which violates the condition that all 'a's must come before all 'b's. If "ba" is not found, then the string satisfies the requirement.

Intuition

When we need all 'a's to appear before all 'b's, we can think about what pattern would violate this rule.

If we imagine the valid strings, they would look like: "aaa...bbb" where all 'a's are grouped at the beginning and all 'b's are grouped at the end. The string could also be all 'a's or all 'b's.

What would make a string invalid? It would be when we have at least one 'b' followed by an 'a'. This is because if any 'b' comes before any 'a', it means not all 'a's are before all 'b's.

The key insight is that we don't need to track positions or count characters. We just need to check if there's ever a situation where 'b' is immediately followed by 'a'. This pattern can be represented as the substring "ba".

If "ba" exists anywhere in the string, it means we have found a violation - a 'b' that comes before an 'a'. If "ba" doesn't exist, then the string must be in one of these valid forms:

• All 'a's
• All 'b's
• Some 'a's followed by some 'b's

This reduces the entire problem to a simple substring search: return "ba" not in s.

Solution Approach

The implementation is remarkably simple and elegant, using a pattern recognition approach rather than traditional iteration or counting methods.

The solution leverages Python's built-in substring search functionality with the in operator. Here's how it works:

1. Pattern Detection: We check for the presence of the substring "ba" in the string s.

2. Boolean Logic: The expression "ba" not in s returns:

   • True if the substring "ba" is not found anywhere in s
   • False if the substring "ba" exists in s

3. Why this works:

   • If "ba" exists in the string, it means there's at least one position where a 'b' is immediately followed by an 'a', violating our requirement
   • If "ba" doesn't exist, the string can only have these patterns:
     • Pure 'a's: "aaaa"
     • Pure 'b's: "bbbb"
     • 'a's followed by 'b's: "aaabbb"

   All these patterns satisfy the condition that every 'a' appears before every 'b'.

The time complexity is O(n) where n is the length of the string, as the substring search needs to examine the string. The space complexity is O(1) since we only use a constant amount of extra space for the substring pattern "ba".

This approach is superior to alternatives like:

• Tracking the last position of 'a' and first position of 'b'
• Using two pointers or multiple passes
• Counting characters and validating positions

The solution transforms a seemingly complex validation problem into a simple pattern matching task.

Example Walkthrough

Let's walk through the solution approach with a few examples to understand how checking for the substring "ba" determines if all 'a's come before all 'b's.

Example 1: s = "aaabbb"

• We check if "ba" exists in "aaabbb"
• Scanning through: "aa", "aa", "ab", "bb", "bb" - no "ba" pattern found
• Since "ba" is not in the string, we return true
• This is correct because all 'a's (positions 0-2) come before all 'b's (positions 3-5)

Example 2: s = "abab"

• We check if "ba" exists in "abab"
• Scanning through: "ab", "ba" - found "ba" at position 1-2!
• Since "ba" exists in the string, we return false
• This is correct because there's a 'b' at position 1 that comes before an 'a' at position 2

Example 3: s = "bbaaa"

• We check if "ba" exists in "bbaaa"
• Scanning through: "bb", "ba" - found "ba" at position 1-2!
• Since "ba" exists in the string, we return false
• This is correct because the 'b's at positions 0-1 come before the 'a's at positions 2-4

Example 4: s = "aaa"

• We check if "ba" exists in "aaa"
• Scanning through: "aa", "aa" - no "ba" pattern found
• Since "ba" is not in the string, we return true
• This is correct because there are only 'a's, so trivially all 'a's come before all 'b's

The key insight is that the substring "ba" acts as a violation detector. Its presence immediately tells us that at least one 'b' comes before at least one 'a', making the string invalid. Its absence guarantees that the string follows the valid pattern of all 'a's before all 'b's.

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the string s. This is because the in operator in Python performs a substring search, which in the worst case needs to examine each character of the string. Specifically, checking if "ba" is not in s requires scanning through the string to find any occurrence of the pattern "ba".

The space complexity is O(1). The algorithm only uses a constant amount of extra space regardless of the input size. The substring search operation doesn't create any additional data structures that scale with the input size - it only needs to keep track of the current position and pattern matching state, which requires constant space.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Misunderstanding the Problem Requirements

A common misconception is thinking that 'a' and 'b' characters must be consecutive or that there must be both characters present. The problem allows for:

• Strings with only 'a's ("aaa" → true)
• Strings with only 'b's ("bbb" → true)
• Empty strings (though not explicitly mentioned, "" → true)

Solution: Remember that the condition is "all 'a's before all 'b's" which is vacuously true when one type of character is absent.

2. Over-engineering with Multiple Passes

Developers might instinctively write complex solutions like:

def checkString(self, s: str) -> bool:
    last_a = -1
    first_b = len(s)
    for i, char in enumerate(s):
        if char == 'a':
            last_a = i
        elif char == 'b' and first_b == len(s):
            first_b = i
    return last_a < first_b

This approach uses more code, is harder to read, and is more error-prone (edge cases with indices).

Solution: Recognize that pattern matching ("ba" not in s) elegantly handles all cases in a single expression.

3. Incorrect Pattern Assumptions

Some might check for patterns like:

• "ab" exists (wrong - this would be valid as 'a' comes before 'b')
• Count of 'a's equals count of 'b's (irrelevant to the problem)
• String must start with 'a' and end with 'b' (too restrictive)

Solution: Focus on what violates the condition: any 'b' followed by any 'a' anywhere in the string.

4. Performance Concerns with Pattern Matching

Developers might worry that substring search is inefficient compared to a single pass that tracks state:

def checkString(self, s: str) -> bool:
    seen_b = False
    for char in s:
        if char == 'b':
            seen_b = True
        elif char == 'a' and seen_b:
            return False
    return True

While this explicitly shows the logic, both approaches have O(n) time complexity. The pattern matching approach is more concise and leverages optimized built-in functions.

Solution: Trust that Python's substring search is highly optimized (uses algorithms like Boyer-Moore or similar) and prioritize code clarity unless profiling shows a real bottleneck.