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

Difficulty: Easy | Acceptance: 73.20% | Paid: No Topics: String

Given a string s consisting of only characters ‘a’ and ‘b’, return true if every ‘a’ appears before every ‘b’, otherwise return false.

Table of Contents

• Examples
• Constraints
• Approach 1: Find Last A and First B
• Approach 2: Single Pass Scan
• Approach 3: Substring Check

Examples

Example 1

Input: s = "aaabbb"
Output: true
Explanation:
The 'a's are at indices 0, 1, 2, while the 'b's are at indices 3, 4, 5.
Hence, every 'a' appears before every 'b'.

Example 2

Input: s = "abab"
Output: false
Explanation:
There is an 'a' at index 3 and a 'b' at index 2.
Hence, not every 'a' appears before every 'b'.

Example 3

Input: s = "bbb"
Output: true
Explanation:
There are no 'a's, so the condition holds vacuously.

Constraints

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

Approach 1: Find Last A and First B

Intuition If the last occurrence of ‘a’ happens before the first occurrence of ‘b’, then all ‘a’s are before all ‘b’s. We can find these two indices and compare them.

Steps

• Iterate through the string to find the index of the last ‘a’. If no ‘a’ exists, treat its index as -1.
• Iterate through the string to find the index of the first ‘b’. If no ‘b’ exists, treat its index as s.length.
• Return true if the last index of ‘a’ is less than the first index of ‘b’, otherwise return false.

class Solution:
    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
            
        for i, char in enumerate(s):
            if char == 'b':
                first_b = i
                break
                
        return last_a < first_b

Complexity

• Time: O(n) - We iterate through the string twice.
• Space: O(1) - We only use a few variables for indices.
• Notes: This approach is intuitive but requires two passes over the string.

Approach 2: Single Pass Scan

Intuition We can iterate through the string once. If we encounter a ‘b’, we know that no ‘a’ should appear after it. We can use a flag to track if we have seen a ‘b’.

Steps

• Initialize a boolean flag seenB to false.
• Iterate through each character in the string:
  • If the character is ‘b’, set seenB to true.
  • If the character is ‘a’ and seenB is true, it means we found an ‘a’ after a ‘b’, so return false immediately.
• If the loop finishes without returning false, return true.

class Solution:
    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

Complexity

• Time: O(n) - We iterate through the string once.
• Space: O(1) - We only use a boolean flag.
• Notes: This is more efficient than the two-pass approach as it can terminate early upon finding a violation.

Approach 3: Substring Check

Intuition The only pattern that violates the condition is an ‘a’ appearing after a ‘b’. This corresponds to the substring “ba”. If the string contains “ba”, it is invalid; otherwise, it is valid.

Steps

• Check if the string “ba” exists within the input string s.
• Return true if “ba” is not found, and false otherwise.

class Solution:
    def checkString(self, s: str) -> bool:
        return 'ba' not in s

Complexity

• Time: O(n) - The underlying implementation of substring search (e.g., KMP or Boyer-Moore in standard libraries) is linear.
• Space: O(1) - No extra space is used proportional to input size.
• Notes: This is the most concise solution and leverages built-in library functions effectively.