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

EASY

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.

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

Checkout 4 different approaches to solve Check if All A's Appears Before All B's. Click on different approaches to view the approach and algorithm in detail.

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.

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.

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.

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;
    }
}

Complexity Analysis

Time Complexity: 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 Complexity: O(1), as no extra space proportional to the input size is used.

Pros and Cons

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.

Code Solutions

Checking out 3 solutions in different languages for Check if All A's Appears Before All B's. Click on different languages to view the code.

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

Video Solution

Watch the video walkthrough for Check if All A's Appears Before All B's

Data Structures:

String