We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

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

Number: 2243

Difficulty: Easy

Paid? No

Companies: Microsoft

Problem Description

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.

Key Insights

  • The goal is to ensure that no 'a' appears after any 'b'.
  • A single pass through the string is sufficient to verify this condition.
  • Special cases include strings containing only one type of character, which should return true.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the string, as we scan through the string once. Space Complexity: O(1), since only a few auxiliary variables are used.

Solution

The approach is to iterate through each character of the string while maintaining a flag that indicates if a 'b' has been encountered. As soon as a 'b' is seen, if any subsequent 'a' is encountered, the function returns false because it violates the condition. Otherwise, if the entire string is scanned without this violation, the function returns true. This method efficiently uses a single pass over the string and a simple Boolean flag.

Code Solutions

def checkString(s: str) -> bool:
    encountered_b = False  # Flag to indicate if a 'b' has been encountered
    for char in s:
        if char == 'b':
            encountered_b = True  # Mark that a 'b' is found
        elif encountered_b and char == 'a':
            # If an 'a' appears after a 'b', return false immediately
            return False
    return True

# Test examples
print(checkString("aaabbb"))  # Expected output: True
print(checkString("abab"))    # Expected output: False
print(checkString("bbb"))     # Expected output: True
← Back to All Questions