Check if All A's Appears Before All B's - Practice Coding Problems

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

String Easy

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.

In other words, the string should have all 'a' characters grouped together at the beginning (or none at all), followed by all 'b' characters grouped together at the end (or none at all).

Input & Output

Example 1 — All a's before all b's

$ Input: s = "aaabbb"

› Output: true

💡 Note: All 'a' characters (positions 0,1,2) appear before all 'b' characters (positions 3,4,5)

Example 2 — Mixed pattern

$ Input: s = "abab"

› Output: false

💡 Note: The 'a' at position 2 appears after the 'b' at position 1, violating the pattern

Example 3 — Only one character type

$ Input: s = "aaa"

› Output: true

💡 Note: String contains only 'a' characters, so the pattern is valid

Constraints

1 ≤ s.length ≤ 100
s[i] is either 'a' or 'b'

Visualization

Tap to expand

Understanding the Visualization

Input

String containing only 'a' and 'b' characters

Check Pattern

Verify all 'a's come before all 'b's

Output

Return true if pattern is valid, false otherwise

Key Takeaway

🎯 Key Insight: Once you see a 'b', no 'a' should appear afterward for a valid pattern

Asked in

🍎 Apple 15 Ⓜ Microsoft 12

The key insight is that once we encounter a 'b' character, no 'a' should appear afterward. The optimal approach uses a single pass with a boolean flag to track if we've seen 'b', returning false immediately if 'a' appears after 'b' is encountered. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Single Pass - Early Detection	O(n)	O(1)	Scan left to right, if we see 'b' then 'a', return false immediately
Brute Force - Check All Pairs	O(n²)	O(1)	Check every 'a' against every 'b' to ensure 'a' comes first
Two Pointers - Find Critical Positions	O(n)	O(1)	Find last 'a' and first 'b' positions, compare them

Single Pass - Early Detection — Algorithm Steps

Initialize flag to track if 'b' was seen
Scan string left to right
If current char is 'b', set flag
If current char is 'a' and flag is set, return false

Visualization

Tap to expand

Step-by-Step Walkthrough

Scan left to right

Process each character sequentially

Track 'b' seen

Set flag when encountering 'b'

Check violation

If 'a' appears after 'b' flag is set, return false

Code -

solution.c — C

#include <stdio.h>
#include <string.h>
#include <stdbool.h>

bool solution(char* s) {
    bool seenB = false;
    int len = strlen(s);
    for (int i = 0; i < len; i++) {
        if (s[i] == 'b') {
            seenB = true;
        } else if (s[i] == 'a' && seenB) {
            return false;
        }
    }
    return true;
}

int main() {
    char s[1001];
    fgets(s, sizeof(s), stdin);
    // Remove newline character
    s[strcspn(s, "\n")] = 0;
    
    bool result = solution(s);
    printf(result ? "true\n" : "false\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through the string, checking each character once

✓ Linear Growth

Space Complexity

O(1)

Only using one boolean variable to track state

✓ Linear Space

28.5K Views

Medium Frequency

~8 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Single Pass - Early Detection — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler