LeetCode 2124 - Check if All A's Appears Before All B's

The problem gives us a string s that contains only two possible characters, 'a' and 'b'. We must determine whether every 'a' appears before every 'b'. Another way to think about the requirement is this: once we encounter a 'b', we should never see another 'a' later in the string.

leetcodeeasystring

LeetCode Problem 2124

Difficulty: 🟢 Easy
Topics: String

Solution

Problem Understanding

The problem gives us a string s that contains only two possible characters, 'a' and 'b'. We must determine whether every 'a' appears before every 'b'.

Another way to think about the requirement is this: once we encounter a 'b', we should never see another 'a' later in the string. If an 'a' appears after a 'b', the ordering rule is violated and the answer must be false.

For example:

  • "aaabbb" is valid because all 'a' characters come first, followed by all 'b' characters.
  • "abab" is invalid because after seeing a 'b' at index 1, we later encounter another 'a' at index 2.
  • "bbb" is valid because there are no 'a' characters at all, so the condition is trivially satisfied.

The constraints are very small:

  • 1 <= s.length <= 100
  • The string contains only 'a' and 'b'

Since the input size is tiny, almost any straightforward solution will run efficiently. Still, it is useful to design a clean linear-time algorithm.

Important edge cases include:

  • Strings containing only 'a'
  • Strings containing only 'b'
  • A single-character string
  • A transition from 'a' to 'b' exactly once, which is valid
  • Any occurrence of 'a' after a 'b', which must immediately fail

Approaches

Brute Force Approach

A brute-force solution checks every pair of positions in the string. For each 'b', we scan all later characters to verify that none of them is 'a'.

For example, if we are at index i and s[i] == 'b', we inspect every j > i. If we ever find s[j] == 'a', we return false.

This approach is correct because it directly verifies the definition of the problem. However, it repeatedly scans overlapping portions of the string, making it inefficient.

Although the constraints are small enough that this would still pass, we can do better with a single pass.

Optimal Approach

The key observation is that the string is valid if and only if we never encounter an 'a' after seeing a 'b'.

We can scan the string once from left to right while maintaining a boolean flag indicating whether a 'b' has already appeared.

  • If we see a 'b', we set the flag.
  • If we later see an 'a' while the flag is already set, the ordering is invalid and we return false.

If we finish the scan without violating the rule, we return true.

This works in linear time and uses constant extra space.

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(1) Checks every 'b' against all later characters
Optimal O(n) O(1) Single left-to-right scan with a flag

Algorithm Walkthrough

  1. Initialize a boolean variable named seen_b as False.

This variable tracks whether we have already encountered a 'b' while scanning the string. 2. Traverse the string from left to right.

We process each character in order because the problem depends on relative ordering. 3. If the current character is 'b', set seen_b = True.

Once a 'b' appears, every remaining character must also be 'b'. 4. If the current character is 'a' and seen_b is already True, return False.

This means an 'a' appeared after a 'b', violating the required ordering. 5. If the loop completes without returning False, return True.

This means no invalid ordering was found.

Why it works

The algorithm maintains the invariant that before encountering the first 'b', both 'a' and 'b' are acceptable. However, after encountering a 'b', only additional 'b' characters are allowed. The moment an 'a' appears after a 'b', the condition is violated. Since the algorithm checks this rule for every character exactly once, it correctly determines whether the string satisfies the required ordering.

Python Solution

class Solution:
    def checkString(self, s: str) -> bool:
        seen_b = False

        for char in s:
            if char == 'b':
                seen_b = True
            elif seen_b:
                return False

        return True

The implementation follows the exact logic from the algorithm walkthrough.

The variable seen_b records whether a 'b' has already appeared in the scan. We iterate through every character in the string:

  • If the character is 'b', we update the flag.
  • If the character is 'a' while seen_b is already True, we immediately return False.

If no invalid ordering is found by the end of the loop, the function returns True.

This implementation is concise, easy to read, and optimal for the problem.

Go Solution

func checkString(s string) bool {
    seenB := false

    for _, ch := range s {
        if ch == 'b' {
            seenB = true
        } else if seenB {
            return false
        }
    }

    return true
}

The Go implementation mirrors the Python solution closely.

The variable seenB tracks whether a 'b' has appeared. The loop iterates through the string using Go's range syntax. Since the string contains only ASCII characters, handling rune values is straightforward.

No special handling for empty strings is required because the constraints guarantee that the string length is at least 1.

Worked Examples

Example 1

Input:

s = "aaabbb"
Index Character seen_b Before Action seen_b After
0 a False Continue False
1 a False Continue False
2 a False Continue False
3 b False Set seen_b = True True
4 b True Continue True
5 b True Continue True

No invalid 'a' appears after a 'b', so the result is True.

Example 2

Input:

s = "abab"
Index Character seen_b Before Action seen_b After
0 a False Continue False
1 b False Set seen_b = True True
2 a True Return False True

At index 2, an 'a' appears after a 'b', so the string is invalid.

Example 3

Input:

s = "bbb"
Index Character seen_b Before Action seen_b After
0 b False Set seen_b = True True
1 b True Continue True
2 b True Continue True

The string contains no 'a' after a 'b', so the result is True.

Complexity Analysis

Measure Complexity Explanation
Time O(n) The string is scanned exactly once
Space O(1) Only a single boolean variable is used

The algorithm performs a single pass through the input string, making the running time proportional to the length of the string. Since only one boolean flag is maintained regardless of input size, the extra space usage remains constant.

Test Cases

solution = Solution()

assert solution.checkString("aaabbb") == True   # standard valid case
assert solution.checkString("abab") == False    # 'a' appears after 'b'
assert solution.checkString("bbb") == True      # only 'b' characters
assert solution.checkString("aaa") == True      # only 'a' characters
assert solution.checkString("a") == True        # single 'a'
assert solution.checkString("b") == True        # single 'b'
assert solution.checkString("ab") == True       # smallest valid mixed case
assert solution.checkString("ba") == False      # smallest invalid mixed case
assert solution.checkString("aabbbb") == True   # multiple grouped characters
assert solution.checkString("bbaa") == False    # invalid because 'a' follows 'b'
assert solution.checkString("aaaaab") == True   # one trailing 'b'
assert solution.checkString("bbbbb") == True    # all 'b'
assert solution.checkString("abaa") == False    # invalid transition back to 'a'
Test Why
"aaabbb" Standard valid ordering
"abab" Detects invalid interleaving
"bbb" Handles strings with no 'a'
"aaa" Handles strings with no 'b'
"a" Single-character lower boundary
"b" Single-character lower boundary
"ab" Smallest valid mixed string
"ba" Smallest invalid mixed string
"aabbbb" Valid grouped ordering
"bbaa" Invalid because 'a' appears later
"aaaaab" Valid with one final 'b'
"bbbbb" Repeated 'b' characters only
"abaa" Multiple invalid transitions

Edge Cases

One important edge case is a string containing only 'a' characters, such as "aaa". A buggy implementation might incorrectly expect at least one 'b' to appear. In reality, the condition is satisfied because there are no 'b' characters that violate the ordering. The algorithm handles this naturally because seen_b never becomes True.

Another important case is a string containing only 'b' characters, such as "bbb". Since there are no 'a' characters after any 'b', the string is valid. The implementation correctly processes this because seeing additional 'b' characters never triggers a failure.

A particularly tricky edge case is when the string switches back to 'a' after a 'b', such as "abaa" or "ba". This is exactly the invalid condition the algorithm is designed to detect. Once seen_b becomes True, any later 'a' immediately causes the function to return False.

A final edge case is the smallest possible input size, such as "a" or "b". Since the constraints allow strings of length 1, the algorithm must correctly handle these minimal inputs. The single-pass scan works correctly even when the loop executes only once.