Teaching Kids Programming – Check if All A’s Appears Before All B’s (itertools.groupby)

Teaching Kids Programming: Videos on Data Structures and Algorithms

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.

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

Algorithms to Check if All A’s Appears Before All B’s

We can invalidate the result (think inversely) once we find a ‘ba’ substring in the original string – which takes O(N) time e.g. using KMP (which requires O(M) time to build a table)

1
2
3

class Solution:
    def checkString(self, s: str) -> bool:
        return "ba" not in s

class Solution:
    def checkString(self, s: str) -> bool:
        return "ba" not in s

We can also group the same consecutive characters using itertools.groupby function. If only 1 group found we return True as it could be either a’s or b’s. If there is more than 2 groups, we return False as it could be ‘aba…’ or ‘bab….’ neither are ok.

The itertools.groupby returns an iterator to the “group keys” and the values are actual group. It is not a dictionary (as dictionary contains only unique keys), but an iterator to subgroups/iterator (where first value is the “key” and second value is also an iterator to the actual group – see below example.

1
2
3
4
5
6
7
8
9

s = "abbaabbb"
 
for i,j in itertools.groupby(s):
     print(i, list(j))
 
a ['a']
b ['b', 'b']
a ['a', 'a']
b ['b', 'b', 'b']

s = "abbaabbb"

for i,j in itertools.groupby(s):
     print(i, list(j))
 
a ['a']
b ['b', 'b']
a ['a', 'a']
b ['b', 'b', 'b']

If there is two groups, we need to check if it is a…b.. instead of b…a…

1
2
3
4
5
6
7
8
9
10

class Solution:
    def checkString(self, s: str) -> bool:
        if not s:
            return True
        l = [i for i, b in itertools.groupby(s)]
        if len(l) == 1:
            return True
        if len(l) >= 3:
            return False
        return l[0] == 'a'

class Solution:
    def checkString(self, s: str) -> bool:
        if not s:
            return True
        l = [i for i, b in itertools.groupby(s)]
        if len(l) == 1:
            return True
        if len(l) >= 3:
            return False
        return l[0] == 'a'

The time complexity is O(N) linear as imposed by itertools.groupby algorithm.

–EOF (The Ultimate Computing & Technology Blog) —