Problem

Given a string s consisting of only the characters 'a' and 'b', return true _ifevery _'a' _appears beforeevery _'b'in the string. Otherwise, return false.

Examples

Example 1

1
2
3
4
5

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

Example 2

1
2
3
4
5

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

Example 3

1
2
3
4

Input: s = "bbb"
Output: true
Explanation:
There are no 'a's, hence, every 'a' appears before every 'b' and we return true.

Constraints

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

Solution

Method 1 – Single Pass with State Tracking

Intuition

We want to ensure that no ‘a’ appears after any ‘b’. As we scan the string, once we see a ‘b’, any subsequent ‘a’ would violate the rule. We can use a flag to track if a ‘b’ has been seen.

Approach

  1. Initialize a flag to indicate if a ‘b’ has been seen.
  2. Iterate through the string:
    • If the current character is ‘b’, set the flag.
    • If the current character is ‘a’ and the flag is set, return false.
  3. If the loop completes, return true.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
    public boolean checkString(String s) {
        boolean seenB = false;
        for (char c : s.toCharArray()) {
            if (c == 'b') seenB = true;
            if (c == 'a' && seenB) return false;
        }
        return true;
    }
}
1
2
3
4
5
6
7
8
9

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

Complexity

  • ⏰ Time complexity: O(n), where n is the length of the string.
  • 🧺 Space complexity: O(1)