Scale Engineer

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

Easy
#1934Time: 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.
Data structures
String

Prompt

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

4 approaches with complexity analysis and trade-offs.

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.

Walkthrough

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

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.

Trade-offs

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.

Solutions

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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem