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

In this leetcode problem, we want to know if all As appear before all Bs in a string.

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.

For example:

"aaa" => true
"bbb" => true
"" => true
"ba" => false
"aababb" => false

To solve the problem, we read the string in order (from left to right). When we encounter the first b, we change the our state, so that we can only see Bs from now on. If we encounter an a after we have already seen a b, we return false. If we finish the string without having returned false, we return true.

This can also be represented in the form of a state machine as follows:

State machine

At the beginning we are in the “Read As” state. As long as we read As, the state stays the same. When we encounter the first b, we change to the “Reas Bs” state. As long as we read Bs, the state stays the same. If we encounter a we go to the “invalid” state, and return false. At the end, if we are in state “read As” or “read Bs”, we return true.

This can be written in C as follows:

bool checkString(char * s){
    int n = strlen(s);
    // 0: reads As
    // 1: reads Bs
    int state…