DEV Community

Cover image for 2124. Check if All A's Appears Before All B's
MD ARIFUL HAQUE
MD ARIFUL HAQUE

Posted on

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

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

Difficulty: Easy

Topics: Mid Level, String, Weekly Contest 274

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. Example 4:
  • Input: s = "aaa"

  • Output: true

  • Explanation:

    • There are no 'b's, hence, every 'a' appears before every 'b' and we return true.

Example 5:

  • Input: s = "ba"
  • Output: false
  • Explanation:
    • The 'b' is at index 0 and the 'a' is at index 1.
    • Hence, a 'b' appears before an 'a', so we return false.

Example 6:

  • Input: s = "ab"
  • Output: true
  • Explanation:
    • The 'a' is at index 0 and the 'b' is at index 1.
    • Hence, every 'a' appears before every 'b' and we return true.

Example 7:

  • Input: s = "a"
  • Output: true
  • Explanation:
    • There is only one 'a' and no 'b's.
    • Hence, every 'a' appears before every 'b' and we return true.

Example 8:

  • Input: s = "b"
  • Output: true
  • Explanation:
    • There is only one 'b' and no 'a's.
    • Hence, every 'a' appears before every 'b' and we return true.

Example 9:

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

Example 10:

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

Example 11:

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

Example 12:

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

Constraints:

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

Hint:

  1. You can check the opposite: check if there is a ‘b’ before an ‘a’. Then, negate and return that answer.
  2. s should not have any occurrences of “ba” as a substring.

Similar Questions:

  1. 1653. Minimum Deletions to Make String Balanced
  2. 1752. Check if Array Is Sorted and Rotated
  3. 2042. Check if Numbers Are Ascending in a Sentence

Solution:

We determine whether every 'a' appears before every 'b' by checking whether the substring "ba" exists in s. If "ba" exists, then a 'b' appears before an 'a', so the answer is false. Otherwise, the answer is true.

Approach

  • Use PHP’s strpos($s, 'ba') to search for the forbidden substring "ba".
  • If strpos returns false, there is no 'b' before an 'a', so return true.
  • If strpos returns a position, then "ba" exists, so return false.
  • Use strict comparison === false because strpos can return 0, which is a valid position but would be loosely equal to false.

Let's implement this solution in PHP: 2124. Check if All A's Appears Before All B's

<?php
/**
 * @param String $s
 * @return Boolean
 */
function checkString(string $s): bool
{
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
echo checkString("aaabbb") ? 'true' : 'false' .  "\n";             // Output: true
echo checkString("abab") ? 'true' : 'false' .  "\n";               // Output: false
echo checkString("bbb") ? 'true' : 'false' .  "\n";                // Output: true
echo checkString("aaa") ? 'true' : 'false' .  "\n";                // Output: true
echo checkString("ba") ? 'true' : 'false' .  "\n";                 // Output: false
echo checkString("ab") ? 'true' : 'false' .  "\n";                 // Output: true
echo checkString("a") ? 'true' : 'false' .  "\n";                  // Output: true
echo checkString("b") ? 'true' : 'false' .  "\n";                  // Output: true
echo checkString("aabbb") ? 'true' : 'false' .  "\n";              // Output: true
echo checkString("bbaa") ? 'true' : 'false' .  "\n";               // Output: false
echo checkString("abba") ? 'true' : 'false' .  "\n";               // Output: false
echo checkString("aabb") ? 'true' : 'false' .  "\n";               // Output: true
?>
Enter fullscreen mode Exit fullscreen mode

Explanation

  • The condition “every 'a' appears before every 'b'” is equivalent to saying there is no 'b' before an 'a'.
  • For a string containing only 'a' and 'b', having a 'b' before an 'a' is equivalent to having "ba" as a substring.
  • If "ba" exists, there is a violation: a 'b' occurs before an 'a'.
  • If "ba" does not exist, the string must be of the form all 'a's followed by all 'b's, possibly with only one character type present.
  • Strings containing only 'a's or only 'b's should return true.

Complexity Analysis

  • Time Complexity: O(n), where n is the length of s. strpos scans the string to find "ba".
  • Space Complexity: O(1), since no extra data structures are used.

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!
Buy Me A Coffee

If you want more helpful content like this, feel free to follow me:

Top comments (0)