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

EasyString

Problem Description

In this problem, we are given a string s that contains only two characters: 'a' and 'b'. The objective is to determine whether all the 'a' characters in the string appear before any 'b' character. If this condition is met, the function should return true, indicating that the string maintains the order where all 'a's come before all 'b's. If this condition is not met, the function should return false. This is a straightforward problem that checks for a specific ordering of characters within a string.

Intuition

The intuition behind the solution is based on a simple observation about the string's character order. If at any point in the string a 'b' appears before an 'a', then not every 'a' is before every 'b', and thus we should return false. A simple way to check this is to look for the substring "ba" within s. If "ba" is found, it means there is an occurrence where 'b' comes directly before 'a', which violates our condition, and as a result, we should return false. On the other hand, if "ba" is not found, it means that all 'a' characters, if present, come before any 'b' character, enabling us to return true.

The provided solution takes advantage of the built-in string operation in Python that checks for the presence of a substring within a string. By using the expression "ba" not in s, we verify if "ba", which is the pattern we don't want to see, is absent from s. If the pattern is absent, it means that the string s satisfies the condition and therefore the function returns true. If the pattern is present, the expression evaluates to false, which means the condition is not met, and the function will return false.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which of the following shows the order of node visit in a Breadth-first Search?

I don’t know

Solution Approach

The implementation of the solution uses a straightforward approach without the need for complex algorithms or data structures. It leverages a simple string scanning feature intrinsic to Python.

Algorithm:

We scan the string s for the substring "ba".
If "ba" is found, it indicates that there is at least one 'b' that comes before an 'a'.
The implementation checks for the non-existence of "ba" to ensure all 'a's come before any 'b's.

Patterns Used:

String Search Pattern: This solution uses a string search to find a specific sequence of characters within another string. In Python, this is commonly done using the in keyword, which checks for the membership of a substring within a larger string.

Code Explanation:

return "ba" not in s: This line of code is the entire implementation. It checks whether the substring "ba" does not exist in the input string s. If the substring "ba" is not found, it implies that the string s maintains the correct order of characters as per the problem statement and thus returns true. Otherwise, it returns false.

This method is extremely efficient because it utilizes Python's built-in string operations, which are highly optimized for these kinds of operations. No additional space is required, as we are not storing any additional data structures, making the space complexity O(1). The time complexity is O(n), where n is the length of the string s, since the search operation has to potentially check each character in the string one by one in the worst-case scenario.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Example Walkthrough

Let's consider the example string s = "aaabb". To illustrate the solution approach, we will apply the algorithm step by step.

The string s is scanned for the substring "ba".
As we go through the string from the start, we see that it begins with 3 'a' characters followed by 2 'b' characters. The substring "ba" does not occur at any point in this string. There is no 'b' that appears before an 'a'. Thus, the condition for the string to maintain that all 'a's come before any 'b's is satisfied.
Since the substring "ba" is not found in s, we conclude that all 'a' characters appear before all 'b' characters.
The expression "ba" not in s is evaluated. Since "ba" indeed does not exist in s, the expression evaluates to true.
Since the expression evaluates to true, the function would return true, correctly indicating that the input string s maintains the order where all 'a's come before any 'b's.

In this example, we have followed the string search pattern methodology as detailed in the solution approach. The immediate absence of "ba" signifies that the order is maintained, thereby allowing the approach to quickly determine the correct result without the need for additional checks or data structures.

Solution Implementation

1class Solution:
2    def check_string(self, s: str) -> bool:
3        # Check if the string 's' does not contain the substring "ba"
4        # If "ba" is not present, it means all 'b's are after 'a's which is valid
5        return "ba" not in s
6

1// Class definition
2class Solution {
3    // Method to check if the input string 's' does NOT contain the substring "ba"
4    public boolean checkString(String s) {
5        // If the string 's' contains "ba", return false
6        // otherwise, return true
7        return !s.contains("ba");
8    }
9}
10

1class Solution {
2public:
3    // Function to check if the string 's' contains the substring "ba".
4    // It returns true if "ba" is not present; otherwise, it returns false.
5    bool checkString(string s) {
6        // Find the first occurrence of "ba" in the string 's'
7        size_t position = s.find("ba");
8      
9        // If "ba" is not found, string::npos is returned
10        // string::npos is a constant representing a non-position
11        // If "ba" is not present, we return true;
12        // otherwise, we return false
13        return position == string::npos;
14    }
15};
16

1// Function to check if the string 's' contains the substring "ba".
2// It returns true if "ba" is not present; otherwise, it returns false.
3function checkString(s: string): boolean {
4    // Find the first occurrence of "ba" in the string 's'
5    let position: number = s.indexOf("ba");
6  
7    // If "ba" is not found, indexOf returns -1
8    // If "ba" is not present, we return true;
9    // otherwise, we return false
10    return position === -1;
11}
12

Not Sure What to Study? Take the 2-min Quiz：

What's the output of running the following function using the following tree as input?

1def serialize(root):
2    res = []
3    def dfs(root):
4        if not root:
5            res.append('x')
6            return
7        res.append(root.val)
8        dfs(root.left)
9        dfs(root.right)
10    dfs(root)
11    return ' '.join(res)
12

1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4    StringJoiner res = new StringJoiner(" ");
5    serializeDFS(root, res);
6    return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10    if (root == null) {
11        result.add("x");
12        return;
13    }
14    result.add(Integer.toString(root.val));
15    serializeDFS(root.left, result);
16    serializeDFS(root.right, result);
17}
18

1function serialize(root) {
2    let res = [];
3    serialize_dfs(root, res);
4    return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8    if (!root) {
9        res.push("x");
10        return;
11    }
12    res.push(root.val);
13    serialize_dfs(root.left, res);
14    serialize_dfs(root.right, res);
15}
16

1 2 3 6 x x1 2 3 x x x 6 x x1 2 6 x x x 3 x x

I don’t know

Time and Space Complexity

The time complexity of the code is O(n), where n is the length of the string s. This is because in the worst case, the in operator needs to check each pair of consecutive characters in the string until it either finds the substring "ba" or confirms that the substring is not present.

The space complexity of the code is O(1) since the amount of additional memory used does not depend on the size of the input string. The method uses a fixed amount of space to store the return value and any temporary variables, which does not scale with the input size.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

What are the most two important steps in writing a depth first search function? (Select 2)

Determine state to pass down to recursive function callDetermine return valueDetermine how many recursive calls will be madeTracing the recursive calls

Overview

Basic Data Structures

Basic Algorithms

Overview

Sorted Array

Implicitly Sorted Array

Advanced

Speedrun

Introduction

DFS on Tree

Binary Search Tree

Advanced

Combinatorial Search

Pruning

Additional States

Aggregation and Memoization

Dedup

Additional Practices

Speedrun

Introduction

BFS on Tree

Introduction

Vanilla BFS

Matrix as Graph

Implicit Graph

Directed Graph / Topological Sort

Weighted Graph

Minimum Spanning Tree

Speedrun

Introduction

Same Direction

Opposite Direction

Sliding Window

Prefix Sum

Cycle Finding

Advanced

Speedrun

Introduction

Top K

Moving Best

Multiple Heaps

Introduction

Grid

Dynamic number of subproblems

Interval

Dual-Sequence

Knapsack

Bitmask

Additional Practices

Disjoint Set Union | Union Find

Trie

Data Structure Design

Segment Tree

Interval

Monotonic Stack

Divide and Conquer

Line Sweep

Tree Traversal without Recursion

Greedy

Math

Matrix

Classics

Concepts

Projects

Amazon OA

Microsoft OA

Google OA

Twitter OA

Editorials

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

Problem Description

Intuition

Solution Approach

Algorithm:

Patterns Used:

Code Explanation:

Example Walkthrough

Solution Implementation

Time and Space Complexity

Recommended Readings