{x}
blog image

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

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.

 

Example 1:

Input: s = "aaabbb"
Output: true
Explanation:
The 'a's are at indices 0, 1, and 2, while the 'b's are at indices 3, 4, and 5.
Hence, every 'a' appears before every 'b' and we return true.

Example 2:

Input: s = "abab"
Output: false
Explanation:
There is an 'a' at index 2 and a 'b' at index 1.
Hence, not every 'a' appears before every 'b' and we return false.

Example 3:

Input: s = "bbb"
Output: true
Explanation:
There are no 'a's, hence, every 'a' appears before every 'b' and we return true.

 

Constraints:

  • 1 <= s.length <= 100
  • s[i] is either 'a' or 'b'.

Solution Explanation

The problem asks whether all occurrences of 'a' come before all occurrences of 'b' in a given string s containing only 'a's and 'b's. The most efficient solution leverages the fact that if a 'b' appears before an 'a', the condition is violated. Therefore, we only need to check if the substring "ba" exists within the input string.

Approach

The core idea is to search for the substring "ba" within the input string s. If "ba" is found, it means a 'b' appears before an 'a', so the function should return false. If "ba" is not found, it means all 'a's appear before all 'b's, and the function returns true.

Code Explanation (Python3, Java, C++, Go)

All four code snippets use a similar approach: they check if the substring "ba" is present in the input string s. The specific methods for this check differ slightly based on the language:

  • Python: 'ba' not in s directly checks for the absence of "ba" using Python's in operator, returning True if "ba" is not found and False otherwise. This is concise and readable.

  • Java: !s.contains("ba") uses the contains() method of the String class, which returns true if the string contains the specified substring. The ! operator negates the result, providing the desired boolean outcome.

  • C++: s.find("ba") == string::npos utilizes the find() method of the string class. find() returns the index of the first occurrence of the substring; if the substring is not found, it returns string::npos. The comparison checks for this "not found" condition.

  • Go: !strings.Contains(s, "ba") employs the Contains() function from the strings package, similar to Java's contains(). The ! operator inverts the result to match the problem's requirements.

Time and Space Complexity

Time Complexity: O(n), where n is the length of the string s. This is because the contains or find operation (or equivalent) has a linear time complexity in the worst case (it might need to scan the entire string).

Space Complexity: O(1). The solution uses only a constant amount of extra space regardless of the input string's size. No additional data structures are allocated that scale with the input size.

This solution is highly efficient because it avoids unnecessary iterations or complex data structures. It directly addresses the problem's core condition by checking for the presence of "ba".