2124. Check if All A's Appears Before All B's Solution

Q: Is Check if All A's Appears Before All B's easy or hard?

Check if All A's Appears Before All B's is classified as an Easy problem. It focuses on basic string iteration and condition checking rather than advanced algorithms or data structures.

Q: How to solve Check if All A's Appears Before All B's in O(n)?

Iterate through the string while tracking whether a 'b' has already appeared. When you encounter 'b', set a flag. If you later see 'a' while the flag is true, the ordering rule is broken and the answer is false. If the loop finishes without violations, return true.

Q: Check if All A's Appears Before All B's Python or Java solution

Both Python and Java implementations follow the same logic: iterate through the string and track whether a 'b' has been seen. If an 'a' appears afterward, return false. The algorithm remains O(n) time and O(1) space regardless of language.

Q: What is the best approach for Check if All A's Appears Before All B's?

The best approach is a one-pass iteration with a boolean flag. Traverse the string once and mark when a 'b' appears. If an 'a' occurs after that point, return false immediately. This method runs in O(n) time with O(1) space and clearly expresses the ordering rule.

Q: What data structure is used in Check if All A's Appears Before All B's?

The problem mainly uses simple string traversal and a boolean flag. No complex data structures are required. The algorithm processes characters sequentially from the input string and checks ordering conditions.

Q: What is the time complexity of Check if All A's Appears Before All B's?

The optimal solution runs in O(n) time because it scans the string once from left to right. Each character is processed exactly once. Space complexity is O(1) since only a single flag variable is needed.

Q: Is Check if All A's Appears Before All B's asked at Google, Amazon, or Meta?

Problems like this appear frequently in screening rounds at large tech companies because they test basic string traversal and reasoning about order constraints. While the exact problem ID may not appear, similar string validation questions are common in interviews at companies such as Amazon and Google.

The 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'.

Approach overview

Problem Overview: Given a string containing only characters 'a' and 'b', verify that every 'a' appears before any 'b'. The moment an 'a' appears after a 'b', the rule is violated and the result should be false.

Approach 1: One-Pass Iteration Using a Flag (O(n) time, O(1) space)

The simplest solution scans the string once from left to right. Maintain a boolean flag that records whether a 'b' has already appeared. While iterating, if you see 'b', set the flag. If you later encounter 'a' while the flag is already set, the order constraint is broken and you return false. If the scan finishes without this violation, the string satisfies the requirement.

This approach works because the condition only depends on relative order, not positions or counts. A single pass over the string is enough to detect the first invalid pattern. It avoids extra data structures and keeps memory usage constant. This is the typical solution used in interviews because it is straightforward and optimal.

Approach 2: Using Regex Match (O(n) time, O(1) space)

A pattern-based solution uses a regular expression that matches valid strings. The only valid form is zero or more 'a' characters followed by zero or more 'b' characters. The regex pattern ^a*b*$ enforces exactly that structure.

Run a full string match using this pattern. If the match succeeds, all 'a' characters appear before all 'b' characters. If it fails, there must be a substring like "ba" that violates the ordering rule. Modern regex engines process this pattern in linear time for this case, so the time complexity remains O(n).

This approach relies on the language’s regex engine instead of manual iteration. It produces very compact code but hides the actual logic behind the pattern. In coding interviews, this method may be acceptable but interviewers usually prefer seeing the explicit algorithm.

Recommended for interviews: The one-pass flag approach is the expected solution. It demonstrates clear reasoning about ordering constraints and uses constant space with O(n) time. The regex solution is concise but less explicit, so it is better suited for quick scripting rather than explaining your thought process during interviews.

Approach 1: One-Pass Iteration Using a Flag

This approach uses a single iteration through the string and a flag variable to determine if all 'a's appear before all 'b's. The flag is set when the first 'b' is encountered. If an 'a' is found after the flag is set, the function returns false. Otherwise, it returns true, as all 'a's appear before 'b's.

Python

def check_order(s: str) -> bool:
    b_found = False
    for char in s:
        if char == 'b':
            b_found = True
        elif char == 'a' and b_found:
            return False
    return True

Java

public class Solution {
    public boolean checkOrder(String s) {
        boolean bFound = false;
        for (char c : s.toCharArray()) {
            if (c == 'b') {
                bFound = true;
            } else if (c == 'a' && bFound) {
                return false;
            }
        }
        return true;
    }
}

C++

#include <string>

bool checkOrder(std::string s) {
    bool bFound = false;
    for (char c : s) {
        if (c == 'b') {
            bFound = true;
        } else if (c == 'a' && bFound) {
            return false;
        }
    }
    return true;
}

JavaScript

function checkOrder(s) {
    let bFound = false;
    for (let char of s) {
        if (char === 'b') {
            bFound = true;
        } else if (char === 'a' && bFound) {
            return false;
        }
    }
    return true;
}

#include <stdbool.h>

bool checkOrder(const char *s) {
    bool bFound = false;
    for (int i = 0; s[i] != '\0'; i++) {
        if (s[i] == 'b') {
            bFound = true;
        } else if (s[i] == 'a' && bFound) {
            return false;
        }
    }
    return true;
}

public class Solution {
    public bool CheckOrder(string s) {
        bool bFound = false;
        foreach (char c in s) {
            if (c == 'b') {
                bFound = true;
            } else if (c == 'a' && bFound) {
                return false;
            }
        }
        return true;
    }
}

This Python function uses a flag to determine if all 'a's appear before all 'b's. The flag is set to true when a 'b' is encountered, and if any 'a' appears after setting this flag, it returns False.

Complexity

Time Complexity: O(n), where n is the length of string s.
Space Complexity: O(1), as only constant space is used.

Try this approach in the editor

Approach 2: Using Regex Match

An alternative approach uses regular expressions to check if the string matches a pattern of any number of 'a's followed by any number of 'b's. This can be achieved using a regex /^a*b*$/ that ensures 'a's are only followed by 'b's.

Python

import re

def check_order(s: str) -> bool:
    return bool(re.match(r'^a*b*$', s))

Java

import java.util.regex.*;

public class Solution {
    public boolean checkOrder(String s) {
        Pattern pattern = Pattern.compile("^a*b*$");
        Matcher matcher = pattern.matcher(s);
        return matcher.matches();
    }
}

C++

#include <string>
#include <regex>

bool checkOrder(const std::string &s) {
    std::regex pattern("^a*b*$");
    return std::regex_match(s, pattern);
}

JavaScript

function checkOrder(s) {
    return /^a*b*$/.test(s);
}

#include <stdbool.h>
#include <regex.h>

bool checkOrder(const char *s) {
    regex_t regex;
    int result;
    // Compile regex to match ^a*b*$ pattern
    result = regcomp(&regex, "^a*b*$", REG_EXTENDED);
    if (result) {
        return false;
    }
    // Execute regex
    result = regexec(&regex, s, 0, NULL, 0);
    regfree(&regex);
    return result == 0;
}

using System.Text.RegularExpressions;

public class Solution {
    public bool CheckOrder(string s) {
        return Regex.IsMatch(s, "^a*b*$");
    }
}

Python's re.match efficiently checks if the string s only allows 'a' characters before 'b' using regex ^a*b*$.

Complexity

Time Complexity: O(n), considering the length of s.
Space Complexity: O(1), as regex doesn't allocate extra space apart from internal structures.

Try this approach in the editor

Approach 3: Brain Teaser

According to the problem statement, the string s consists only of characters a and b.

To ensure that all as appear before all bs, the condition that must be met is that b should not appear before a. In other words, the substring "ba" should not be present in the string s.

The time complexity is O(n), where n is the length of the string s. The space complexity is O(1).

TypeScript

function checkString(s: string): boolean {
    return !s.includes('ba');
}

func checkString(s string) bool {
	return !strings.Contains(s, "ba")
}

Rust

impl Solution {
    pub fn check_string(s: String) -> bool {
        !s.contains("ba")
    }
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
One-Pass Iteration Using a Flag	Time Complexity: O(n), where n is the length of string `s`. Space Complexity: O(1), as only constant space is used.
Using Regex Match	Time Complexity: O(n), considering the length of `s`. Space Complexity: O(1), as regex doesn't allocate extra space apart from internal structures.
Brain Teaser	–

Complexity analysis

Approach	Time	Space	When to Use
One-Pass Iteration Using a Flag	O(n)	O(1)	Best general solution; interview-friendly and minimal memory usage
Regex Pattern Match (^ab$)	O(n)	O(1)	Useful when regex utilities are allowed and concise code is preferred

Frequently asked questions

Is Check if All A's Appears Before All B's easy or hard?

Check if All A's Appears Before All B's is classified as an Easy problem. It focuses on basic string iteration and condition checking rather than advanced algorithms or data structures.

How to solve Check if All A's Appears Before All B's in O(n)?

Iterate through the string while tracking whether a 'b' has already appeared. When you encounter 'b', set a flag. If you later see 'a' while the flag is true, the ordering rule is broken and the answer is false. If the loop finishes without violations, return true.

Check if All A's Appears Before All B's Python or Java solution

Both Python and Java implementations follow the same logic: iterate through the string and track whether a 'b' has been seen. If an 'a' appears afterward, return false. The algorithm remains O(n) time and O(1) space regardless of language.

What is the best approach for Check if All A's Appears Before All B's?

The best approach is a one-pass iteration with a boolean flag. Traverse the string once and mark when a 'b' appears. If an 'a' occurs after that point, return false immediately. This method runs in O(n) time with O(1) space and clearly expresses the ordering rule.

What data structure is used in Check if All A's Appears Before All B's?

The problem mainly uses simple string traversal and a boolean flag. No complex data structures are required. The algorithm processes characters sequentially from the input string and checks ordering conditions.

What is the time complexity of Check if All A's Appears Before All B's?

The optimal solution runs in O(n) time because it scans the string once from left to right. Each character is processed exactly once. Space complexity is O(1) since only a single flag variable is needed.

Is Check if All A's Appears Before All B's asked at Google, Amazon, or Meta?

Problems like this appear frequently in screening rounds at large tech companies because they test basic string traversal and reasoning about order constraints. While the exact problem ID may not appear, similar string validation questions are common in interviews at companies such as Amazon and Google.

Check if All A's Appears Before All B's solution and explanation

The problem

Approach overview

Approach 1: One-Pass Iteration Using a Flag

Approach 2: Using Regex Match

Approach 3: Brain Teaser

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Check if All A's Appears Before All B's solution and explanation

The problem

Approach overview

Approach 1: One-Pass Iteration Using a Flag

Approach 2: Using Regex Match

Approach 3: Brain Teaser

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems