algoadvance

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

Problem Statement

You are given a string s consisting of only the characters ‘a’ and ‘b’. You need to determine if every ‘a’ in the string appears before every ‘b’. Return true if every ‘a’ appears before every ‘b’, otherwise return false.

Example 1:

• Input: s = “aaabbb”
• Output: true

Example 2:

• Input: s = “abab”
• Output: false

Example 3:

• Input: s = “bbb”
• Output: true

Clarifying Questions

1. Input Constraints:
   • Is the string guaranteed to be non-empty?
   • Should the solution be case-sensitive, or can we assume all characters will be lowercase?
   • What is the maximum length of the string?
2. Output Requirements:
   • Should we return a boolean value?

Strategy

• Iterate through the string.
• Maintain a flag variable that changes when a ‘b’ is encountered.
• If any ‘a’ is found after this flag is set to true, return false.
• If no such ‘a’ is found after encountering ‘b’, return true.

Time Complexity

The time complexity of this approach is O(n), where n is the length of the string. This is because we only make a single pass through the string.

Code

public class Solution {
    public boolean checkString(String s) {
        boolean foundB = false;
        
        // Iterate through each character in the string
        for (char ch : s.toCharArray()) {
            if (ch == 'b') {
                foundB = true;
            }
            // If 'a' is found after 'b', return false
            if (foundB && ch == 'a') {
                return false;
            }
        }
        // If no 'a' is found after 'b', return true
        return true;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();

        // Test cases
        System.out.println(sol.checkString("aaabbb")); // true
        System.out.println(sol.checkString("abab"));   // false
        System.out.println(sol.checkString("bbb"));    // true
        System.out.println(sol.checkString("a"));      // true
        System.out.println(sol.checkString(""));       // true (assuming empty is a valid input)
    }
}

Explanation

• The checkString method initializes a boolean foundB to track if a ‘b’ has been encountered.
• It iterates through each character in the string.
• When a ‘b’ is found, foundB is set to true.
• If foundB is true and an ‘a’ is encountered, it returns false immediately.
• If the loop completes without finding an ‘a’ after a ‘b’, it returns true.

Edge Cases Covered

• All ‘a’s in the string
• All ‘b’s in the string
• Mixed ‘a’s and ‘b’s with the wrong order
• Empty string

This straightforward approach ensures we efficiently check the condition by a single traversal of the string.

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?