algoadvance

Given a string s consisting of only the characters ‘a’ and ‘b’, return True if every ‘a’ in s appears before every ‘b’. Otherwise, return False.

Clarifying Questions

  1. Input Constraints:
    • Is the input string guaranteed to contain only ‘a’ and ‘b’ characters?
    • What is the maximum length of the input string s?
  2. Output:
    • Should we handle edge cases like an empty string or a string with only one type of character?

Assuming:

Strategy

To check if all ‘a’s appear before all ‘b’s, we can use a simple scan of the string:

  1. Traverse the string from left to right.
  2. Once a ‘b’ is encountered, ensure that no ‘a’ appears after it.
  3. If an ‘a’ is found after ‘b’, return False.
  4. Complete the traversal and return True if the condition is satisfied.

Code

def checkString(s: str) -> bool:
    # Flag to indicate if a 'b' has been seen
    b_seen = False
    
    for char in s:
        if char == 'b':
            b_seen = True
        elif char == 'a' and b_seen:
            # If 'a' is found after 'b'
            return False
    
    return True

Time Complexity

The time complexity of this solution is O(n), where n is the length of the string s. The string is traversed exactly once, making this approach efficient even for larger strings.

Explanation of the Code

  1. Initialization: Initialize a flag b_seen to False.
  2. Traversal: Iterate through each character in the string.
    • If the character is ‘b’, set b_seen to True.
    • If the character is ‘a’ and b_seen is True, return False immediately because an ‘a’ has appeared after a ‘b’.
  3. Result: If the loop completes without encountering any ‘a’ after a ‘b’, return True.

This solution ensures that the condition of all ‘a’s appearing before ‘b’s is checked efficiently.

Try our interview co-pilot at AlgoAdvance.com