Jobs

Interviews

Discussions

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

Easy

Asked by:

42 views

Topics:

StringsTwo Pointers

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

Try coding it in LeetCode

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

Easy

Asked by:

42 views

Topics:

StringsTwo Pointers

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

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the input string contain characters other than 'a' and 'b'?
Is the input string case-sensitive? Should I assume all characters are lowercase?
What should I return if the input string is empty or null?
If the string contains only 'a's or only 'b's, should the function return true?
What is the maximum possible length of the input string?

Brute Force Solution

Approach

We want to check if all the letter 'A's come before all the letter 'B's in a sequence. The brute force method involves looking at each 'A' and 'B' and comparing their positions to see if any 'B's come before any 'A's.

Here's how the algorithm would work step-by-step:

Go through each letter in the sequence from left to right.
If you find an 'A', remember its location.
After that, continue looking at the remaining letters.
If you find a 'B', check if any 'A's came after this 'B'. In other words, check if the location of this 'B' is before any 'A' that you previously saw.
If any 'A' comes after a 'B', then the requirement that all 'A's appear before all 'B's is violated. So, if you find such a case, you know the answer is false.
If you get through the entire sequence without finding any 'B' appearing before any 'A', then all 'A's must have come before all 'B's, and the answer is true.

Code Implementation

def check_a_before_b(input_string):
    last_a_position = -1
    
    for current_index in range(len(input_string)):
        if input_string[current_index] == 'A':
            last_a_position = current_index

    for current_index in range(len(input_string)):
        if input_string[current_index] == 'B':
            #If a 'B' is found, check if any 'A' came after it.
            if last_a_position > current_index:

                return False

    return True

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input string of size n once. During this iteration, it keeps track of the index of the last encountered 'A'. Subsequently, upon encountering a 'B', it compares its index against the stored index of the last 'A'. Although this sounds like two loops, it is not. The first loop finds the location of the last A. The second 'loop' is only executed at a maximum of n times when a B is encountered to find if the current 'B' is before the last 'A', resulting in constant time operations O(1). Thus, the dominant operation is the single pass through the string, giving a time complexity of O(n).

Space Complexity

O(1) – The algorithm described in the plain English explanation requires only a constant amount of extra space. It stores, at most, the location of one 'A'. After finding the location of 'A' it iterates through the rest of the string and doesn't store anything else. Therefore, no matter how long the input string is, the memory used by the algorithm remains the same.

Optimal Solution

Approach

The core idea is to find the first 'B' in the string. Once we find it, we ensure that there are no 'A's after that point. This avoids the need to check all possible arrangements of 'A's and 'B's.

Here's how the algorithm would work step-by-step:

Go through the string from beginning to end.
Stop when you find the very first 'B'.
From that point onwards, continue to the end of the string.
If you find an 'A' after the first 'B', it means the string does not meet the requirement, so the answer is 'no'.
If you reach the end of the string without finding any 'A's after the first 'B', it means all 'A's appear before all 'B's, so the answer is 'yes'.

Code Implementation

def check_string(input_string):
    first_b_found = False
    
    for char in input_string:
        if char == 'B':
            # Once first 'B' found, mark it.
            first_b_found = True

        if first_b_found and char == 'A':
            # If we find 'A' after first 'B',
            # it violates the condition.           return False

    # If we reach here, condition is met
    # because there's no 'A' after 'B'   return True

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input string of size n at most twice. The first iteration finds the first occurrence of 'B'. The second iteration, if a 'B' was found, continues from that 'B' to the end of the string, looking for 'A's. In the worst case, it checks every character once to find the first 'B' and then checks the rest of the string to make sure there are no 'A's afterward. Therefore, the time complexity is O(n).

Space Complexity

O(1) – The provided algorithm iterates through the string using index variables, but it doesn't use any auxiliary data structures like arrays, hash maps, or lists to store intermediate results. It only requires a constant amount of extra memory to store the index of the first 'B' encountered (if any) and to traverse the string. Therefore, the space complexity is independent of the input string's length (N) and remains constant.

Edge Cases

Case	How to Handle
Empty string	Return true immediately as there are no A's or B's to violate the condition.
String with only A's	Return true since all A's appear before any (non-existent) B's.
String with only B's	Return true since there are no A's to violate the condition.
String with one character	Return true since a single 'A' or 'B' trivially satisfies the condition.
String with 'B' before 'A'	Return false; this is the main failing condition.
String with many alternating A's and B's	Return false; this tests for the need to check multiple occurrences.
String with leading/trailing whitespace	Trim whitespace from the string before processing to avoid incorrect results based on whitespace characters.
String with characters other than 'A' and 'B'	Reject the input or treat the other characters as invalid, potentially throwing an error or returning false.

Empty string

How to Handle:

Return true immediately as there are no A's or B's to violate the condition.

String with only A's

How to Handle:

Return true since all A's appear before any (non-existent) B's.

String with only B's

How to Handle:

Return true since there are no A's to violate the condition.

String with one character

How to Handle:

Return true since a single 'A' or 'B' trivially satisfies the condition.

String with 'B' before 'A'

How to Handle:

Return false; this is the main failing condition.

String with many alternating A's and B's

How to Handle:

Return false; this tests for the need to check multiple occurrences.

String with leading/trailing whitespace

How to Handle:

Trim whitespace from the string before processing to avoid incorrect results based on whitespace characters.

String with characters other than 'A' and 'B'

How to Handle:

Reject the input or treat the other characters as invalid, potentially throwing an error or returning false.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the input string contain characters other than 'a' and 'b'?
Is the input string case-sensitive? Should I assume all characters are lowercase?
What should I return if the input string is empty or null?
If the string contains only 'a's or only 'b's, should the function return true?
What is the maximum possible length of the input string?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Go through each letter in the sequence from left to right.
If you find an 'A', remember its location.
After that, continue looking at the remaining letters.
If you find a 'B', check if any 'A's came after this 'B'. In other words, check if the location of this 'B' is before any 'A' that you previously saw.
If any 'A' comes after a 'B', then the requirement that all 'A's appear before all 'B's is violated. So, if you find such a case, you know the answer is false.
If you get through the entire sequence without finding any 'B' appearing before any 'A', then all 'A's must have come before all 'B's, and the answer is true.

Code Implementation

def check_a_before_b(input_string):
    last_a_position = -1
    
    for current_index in range(len(input_string)):
        if input_string[current_index] == 'A':
            last_a_position = current_index

    for current_index in range(len(input_string)):
        if input_string[current_index] == 'B':
            #If a 'B' is found, check if any 'A' came after it.
            if last_a_position > current_index:

                return False

    return True

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

The core idea is to find the first 'B' in the string. Once we find it, we ensure that there are no 'A's after that point. This avoids the need to check all possible arrangements of 'A's and 'B's.

Here's how the algorithm would work step-by-step:

Go through the string from beginning to end.
Stop when you find the very first 'B'.
From that point onwards, continue to the end of the string.
If you find an 'A' after the first 'B', it means the string does not meet the requirement, so the answer is 'no'.
If you reach the end of the string without finding any 'A's after the first 'B', it means all 'A's appear before all 'B's, so the answer is 'yes'.

Code Implementation

def check_string(input_string):
    first_b_found = False
    
    for char in input_string:
        if char == 'B':
            # Once first 'B' found, mark it.
            first_b_found = True

        if first_b_found and char == 'A':
            # If we find 'A' after first 'B',
            # it violates the condition.           return False

    # If we reach here, condition is met
    # because there's no 'A' after 'B'   return True

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty string	Return true immediately as there are no A's or B's to violate the condition.
String with only A's	Return true since all A's appear before any (non-existent) B's.
String with only B's	Return true since there are no A's to violate the condition.
String with one character	Return true since a single 'A' or 'B' trivially satisfies the condition.
String with 'B' before 'A'	Return false; this is the main failing condition.
String with many alternating A's and B's	Return false; this tests for the need to check multiple occurrences.
String with leading/trailing whitespace	Trim whitespace from the string before processing to avoid incorrect results based on whitespace characters.
String with characters other than 'A' and 'B'	Reject the input or treat the other characters as invalid, potentially throwing an error or returning false.

Empty string

How to Handle:

Return true immediately as there are no A's or B's to violate the condition.

String with only A's

How to Handle:

Return true since all A's appear before any (non-existent) B's.

String with only B's

How to Handle:

Return true since there are no A's to violate the condition.

String with one character

How to Handle:

Return true since a single 'A' or 'B' trivially satisfies the condition.

String with 'B' before 'A'

How to Handle:

Return false; this is the main failing condition.

String with many alternating A's and B's

How to Handle:

Return false; this tests for the need to check multiple occurrences.

String with leading/trailing whitespace

How to Handle:

Trim whitespace from the string before processing to avoid incorrect results based on whitespace characters.

String with characters other than 'A' and 'B'

How to Handle:

Reject the input or treat the other characters as invalid, potentially throwing an error or returning false.