algoadvance

Leetcode 2124. Check if All A’s Appears Before All B’s

Problem Statement

• Title: Check if All A’s Appears Before All B’s
• Description: Given a string s consisting only of the characters ‘a’ and ‘b’, check if all the ‘a’ characters appear before all the ‘b’ characters in the string.

Example:

Input: "aaabbb"
Output: true

Input: "abab"
Output: false

Clarifying Questions

1. Input Constraints:
   • What is the maximum length of the string s?
   • Are there any invalid characters in the string or is it guaranteed to only contain ‘a’ and ‘b’?
2. Output Requirements:
   • Should the function return a boolean value or a specific format of true and false?

Assuming:

• The input string s will only contain ‘a’ and ‘b’.
• The maximum length of the string would be within typical input size constraints for LeetCode problems (e.g., up to (10^5) characters).
• The function should simply return a boolean value.

Strategy

We need to iterate through the string and check if at any position a character ‘b’ is followed by a character ‘a’. This would mean that ‘a’ does not appear before all ‘b’s, and we should return false in that case.

Pseudocode

1. Iterate through the string character by character.
2. Initialize a flag seenB to false.
3. For each character:
   • If the character is ‘b’, set seenB to true.
   • If the character is ‘a’ and seenB is true, return false immediately.
4. If the loop completes without finding such a condition, return true.

Code

class Solution {
public:
    bool checkString(string s) {
        bool seenB = false;
        for (char c : s) {
            if (c == 'b') {
                seenB = true;
            } else if (c == 'a') {
                if (seenB) {
                    return false;
                }
            }
        }
        return true;
    }
};

Time Complexity

• Time Complexity: (O(n))
  • We iterate through the string exactly once, where (n) is the length of the string.
• Space Complexity: (O(1))
  • We use a constant amount of space irrespective of the input size.

This solution is efficient since it only requires a single pass through the input string, ensuring optimal performance.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?