DDSA Solutions

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

Time: O(n)
Space: O(1)

Problem Overview

The string uses only a and b.

Intuition

The string uses only a and b. Every a must appear before every b, which means once a b shows up you can never see an a again. That forbidden pattern is exactly the two character substring ba. Searching once for ba is therefore enough: if it never occurs the order is valid, and if it does the string fails.

Algorithm

  1. 1Return whether the string does not contain the substring ba.

Example Walkthrough

Input: s = "aaabbb"

  1. 1.The characters stay in a block of a then a block of b.
  2. 2.There is no place where b is immediately followed by a.
  3. 3.The check succeeds, so the answer is true.

Output: true

Common Pitfalls

  • •An empty string or a string of only one letter is valid. There is no ba to find.
  • •Equal counts of a and b are not enough. The order of the characters is what matters.
  • •Any a that appears after some b creates a ba transition in an a/b string, so the substring test is complete.
  • •A linear scan that remembers whether a b was seen is equivalent and also O(n).
2124.cs
C#
// Approach: All a's before all b's means the string never contains the
// substring "ba". A single search for that pattern decides the answer.
// Time: O(n) Space: O(1)

public class Solution
{
    public bool CheckString(string s)
    {
        return !s.Contains("ba");
    }
}
Was this solution helpful?

Related Problems