# Check if All A's Appears Before All B's
**Difficulty:** EASY
[External](https://leetcode.com/problems/check-if-all-as-appears-before-all-bs)
Canonical: https://scaleengineer.com/dsa/problems/check-if-all-a's-appears-before-all-b's
**Data structures:** String
---
## Problem
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`.

**Example 1:**

**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:**

**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:**

**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'`.

# Approaches
## Brute Force with Nested Loops
This is a straightforward brute-force approach that directly checks the condition. The core idea is to find if there is any instance of a 'b' character appearing before an 'a' character. We can achieve this by comparing every 'b' with all the characters that follow it.
**Time:** O(N^2), where N is the length of the string. In the worst case (e.g., `s = "bb...ba"`), the nested loops lead to a quadratic number of comparisons. · **Space:** O(1), as no extra space proportional to the input size is used.
**Pros:** Easy to understand and implement.; Directly translates the problem's inverse condition into code.
**Cons:** Very inefficient with a time complexity of O(N^2).; Will perform poorly on larger strings, potentially leading to a 'Time Limit Exceeded' error in a competitive programming context.
### Explanation
We use two nested loops. The outer loop scans the string to find a 'b'. Once a 'b' is found at index `i`, the inner loop scans the rest of the string from index `i+1`. If the inner loop ever finds an 'a', we have confirmed that not all 'a's appear before all 'b's, and we can immediately return `false`. If the loops finish without finding such a 'b' followed by an 'a', the string is valid, and we return `true`.

```java
class Solution {
    public boolean checkString(String s) {
        int n = s.length();
        for (int i = 0; i < n; i++) {
            if (s.charAt(i) == 'b') {
                for (int j = i + 1; j < n; j++) {
                    if (s.charAt(j) == 'a') {
                        return false;
                    }
                }
            }
        }
        return true;
    }
}
```
### Algorithm
- Iterate through the string with an outer loop using index `i` from `0` to `n-1`.
- If the character at `s[i]` is `'b'`, start an inner loop.
- The inner loop iterates with index `j` from `i + 1` to `n-1`.
- Inside the inner loop, if the character `s[j]` is `'a'`, it means we have found an 'a' that appears after a 'b'. This violates the condition, so we return `false`.
- If both loops complete without finding such a case, it means the condition holds for the entire string, and we can return `true`.

## Find Last 'a' and First 'b'
A more optimized approach is to realize that the condition "every 'a' appears before every 'b'" is equivalent to saying that the index of the last 'a' must be less than the index of the first 'b'. If this holds, all other 'a's (which appear before the last 'a') will also be before all other 'b's (which appear after the first 'b').
**Time:** O(N), where N is the length of the string. Each of the `lastIndexOf` and `indexOf` calls takes linear time to scan the string. · **Space:** O(1), as we only store a couple of integer variables.
**Pros:** Significant improvement in time complexity over the brute-force approach.; Code is clean and easy to read, especially with built-in functions.
**Cons:** May require two passes over the string in the worst case, one for `lastIndexOf` and one for `indexOf`.
### Explanation
This method leverages built-in string searching functions to find the critical indices. We find the index of the last 'a' and the first 'b'. If either character doesn't exist, the condition is trivially true. For example, if there are no 'a's, there's no 'a' that can appear after a 'b'. If both exist, we simply compare their indices. If the last 'a' comes before the first 'b', the string is valid.

```java
class Solution {
    public boolean checkString(String s) {
        int lastA = s.lastIndexOf('a');
        int firstB = s.indexOf('b');

        // If no 'a's or no 'b's, the condition is met.
        if (lastA == -1 || firstB == -1) {
            return true;
        }

        return lastA < firstB;
    }
}
```
### Algorithm
- Find the index of the last occurrence of 'a' in the string. Let's call it `lastA`. Many languages provide a `lastIndexOf` function for this.
- Find the index of the first occurrence of 'b' in the string. Let's call it `firstB`. A `indexOf` function can be used.
- If 'a' is not present in the string (`lastA` is -1), the condition is vacuously true.
- Similarly, if 'b' is not present (`firstB` is -1), the condition is also true.
- If both characters exist, the condition holds if and only if `lastA < firstB`.

## Check for "ba" Substring
This is the most concise and an equally efficient approach. The problem can be reframed: the arrangement is valid if and only if there is no 'b' that is immediately followed by an 'a'. If such a `"ba"` pattern existed, the condition would be violated. If it doesn't exist, then after the first 'b', no 'a' can appear, which means all 'a's must have come before.
**Time:** O(N). The `contains` method performs a linear scan of the string to find the pattern. · **Space:** O(1). The space required for the pattern `"ba"` is constant.
**Pros:** Extremely simple, concise, and readable.; Optimal time and space complexity.; Leverages optimized built-in functions.
**Cons:** Relies on a built-in library function, which might abstract away the underlying implementation details.
### Explanation
We can use the built-in `contains` method available in many languages to check for the existence of the substring `"ba"`. If `s.contains("ba")` is true, it means the condition is violated, so we should return `false`. Otherwise, we return `true`. This leads to a very simple one-line solution.

```java
class Solution {
    public boolean checkString(String s) {
        return !s.contains("ba");
    }
}
```
### Algorithm
- The condition that all 'a's appear before all 'b's is violated if and only if the substring `"ba"` exists in the string.
- If we find a 'b' followed by an 'a', then not all 'a's can be before all 'b's.
- Conversely, if the substring `"ba"` does not exist, it means that once a 'b' is seen, no 'a' can appear after it. This satisfies the condition.
- Therefore, the problem simplifies to checking if `s` contains `"ba"`.
- Return `true` if it does not contain `"ba"`, and `false` if it does.

## Single Pass Scan
The most efficient approach is to iterate through the string just once. We can maintain a state to track whether we've encountered a 'b' character. If we find an 'a' after we've already seen a 'b', we know the condition is violated.
**Time:** O(N), where N is the length of the string, because we iterate through the string at most once. · **Space:** O(1), as we only use a single boolean flag for extra storage.
**Pros:** Optimal time complexity as it requires only a single pass.; Optimal space complexity.; Can terminate early as soon as a violation is found.
**Cons:** Slightly more verbose than the `contains("ba")` approach, but fundamentally the same logic.
### Explanation
We can traverse the string with a single loop and a boolean flag, say `foundB`. This flag will be `false` initially. When we encounter the first 'b', we flip the flag to `true`. From that point on, if we ever encounter an 'a', we know the string is invalid because an 'a' has appeared after a 'b'. If we finish iterating through the entire string without this invalid condition occurring, the string is valid.

```java
class Solution {
    public boolean checkString(String s) {
        boolean foundB = false;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == 'b') {
                foundB = true;
            } else if (c == 'a') {
                // if we find an 'a' and we have already seen a 'b'
                if (foundB) {
                    return false;
                }
            }
        }
        return true;
    }
}
```
### Algorithm
- Initialize a boolean flag, `foundB`, to `false`.
- Iterate through the string from left to right.
- If the current character is `'b'`, set `foundB` to `true`. This indicates that we have reached the part of the string where 'b's can appear.
- If the current character is `'a'`, check the `foundB` flag. If `foundB` is `true`, it means we have found an 'a' after already seeing a 'b'. This is a violation, so we return `false`.
- If the loop completes without returning `false`, it means no 'a' was found after a 'b', so the string is valid. Return `true`.

# Solutions
### Java

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

```

### CPP

```cpp
class Solution {
public:
  bool checkString(string s) { return s.find("ba") == string ::npos; }
};

```

### Python

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

```