Check If All As Appears Before All Bs - Leetcode Solution

Problem:

Given a string s, return true if and only if the letters 'a' and 'b' appear in s in alphabetical order (i.e., 'a' comes before 'b').

Example 1:

Input: s = "ab" Output: true Explanation: The letters 'a' and 'b' appear in alphabetical order.

Example 2:

Input: s = "ba" Output: false Explanation: The letters 'a' and 'b' do not appear in alphabetical order.

Example 3:

Input: s = "abc" Output: true Explanation: The letters 'a', 'b', and 'c' appear in alphabetical order.

Example 4:

Input: s = "cab" Output: false Explanation: The letter 'c' appears before the letter 'a'.

Solution:

To solve this problem, we need to iterate through the string s and check if we encounter a 'b' before we encounter an 'a'. If we do, we know that 'a' and 'b' do not appear in alphabetical order, and we can return false. If we iterate through the string and do not encounter such a case, we can return true.

Algorithm:

1. Initialize a flag to check if we have encountered 'b' before 'a' and set it to false.
2. Loop through each character in the string s.
3. If we encounter a 'b' before 'a' and the flag is still false, set the flag to true.
4. If we encounter an 'a' after the flag is set to true, return false.
5. If we reach the end of the string without encountering such a case, return true.

Pseudo code:

flag = false for i in range(len(s)): if s[i] == 'b' and not flag: flag = true elif s[i] == 'a' and flag: return false return true

Time Complexity:

The time complexity of this algorithm is O(n), where n is the length of the string.

Space Complexity:

The space complexity of this algorithm is O(1), as we are only using a single flag variable to keep track of our progress through the string.

1