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

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. Note that an empty string, a string with only a's, or a string with only b's are all valid.

Input: s = "aaabbb"
Output: true
Explanation: The a's are at indices 0, 1, and 2. The b's are at indices 3, 4, and 5. All a's appear before all b's, so we return true.

Input: s = "abab"
Output: false
Explanation: There is an 'a' at index 2 that appears after a 'b' at index 1.

Input: s = "bbb"
Output: true
Explanation: There are no a's, so the condition is trivially satisfied.

Problem Breakdown:

1. The key insight is that if all a's appear before all b's, then the substring "ba" should never occur in the string. If we ever see a 'b' followed by an 'a', the order is violated.

• # If "ba" exists in the string, the condition is violated

2. One simple approach: check if the string contains "ba" as a substring. If it does, return False. Otherwise return True.

• return "ba" not in s

3. Alternative approach using a flag: iterate through the string. Once we see a 'b', set a flag. If we see an 'a' after the flag is set, we know the condition is violated.

• seenB = False
  for c in s:
      if c == 'b':
          seenB = True
      elif seenB:
          return False

4. After the loop completes without finding an 'a' after a 'b', all a's indeed appear before all b's, so we return True.

• return True

Summary:

The simplest approach checks whether "ba" appears as a substring - if it does, an 'a' comes after a 'b', violating the condition. Alternatively, use a boolean flag to track if we have seen a 'b', and return false if we encounter an 'a' after seeing a 'b'.

Time and Space Complexity:

Time Complexity: O(n) - we iterate through the string once.

Space Complexity: O(1) - we only use a single boolean variable.

Python Solution:

def checkString(s):
    return "ba" not in s

JavaScript Solution:

var checkString = function(s) {
    return !s.includes("ba");
};

Java Solution:

class Solution {
    public boolean checkString(String s) {
        return !s.contains("ba");
    }
}