New update is available. Click here to update.

Overlapping ABBA

PROBLEM STATEMENT

Anish is given a string S and has been asked to determine if the given string S contains two non-overlapping substrings "AB" and "BA" (the substrings can go in any order).

As a friend of Anish, your task is to return “True” if the string S contains two non-overlapping substrings "AB" and "BA" (the substrings can go in any order) otherwise return “False” (without quotes).

Example:-

The string “ABBA” has two non-overlapping substrings “AB” and “BA” respectively. So “True” will be printed(without quotes).

Input format :

The first line contains a single integer T representing the number of test cases.

The first line of each test case contains the string S denoting the given string to Anish.

Output format :

For each test case, print "True"  if the string S contains two non-overlapping substrings "AB" and "BA" (the substrings can go in any order) else print "False” (without quotes).

The output of each test case should be printed in a separate line.

Note:

You are not required to print anything, it has already been taken care of. Just implement the function.

Constraints :

1 <= T <= 10
1 <= |S| <= 10^4
The string S contains uppercase Latin letters only.
Time Limit = 1 sec

Approach 1

We can check the first occurrence of substring “AB” and the last occurrence of substring “BA”. If they don’t overlap, return True. Else, check the first occurrence of substring “BA” and the last occurrence of substring “AB”. If they don’t overlap, return True, else return False.

Algorithm:-

Initialize four variables FirstOccurAB, FirstOccurBA with the value |S|(length of the string S), and LastOccurBA, LastOccurAB with the value -1 to store the first and last occurrences of sub-string “AB” and “BA” respectively.
Run a for loop from 1 to |S|. (Let’s say the iterator is i).
1. If S[i] == ”B” and S[i - 1] == ”A” update LastOccurAB as max(LastOccurAB,i - 1) and FirstOccurAB as min(FirstOccurAB,i).
2. If S[i] == ”A” and S[ i - 1] == ”B” update LastOccurBA as max(LastOccurBA, i - 1) and FirstOccurBA as min(FirstOccurBA,i).
If LastOccurAB is not equal to - 1 and FirstOccurBA is not equal to |S| and LastOccurAB is greater than FirstOccurBA return True.
If LastOccurBA is not equal to - 1 and FirstOccurAB is not equal to |S| and LastOccurBA is greater than FirstOccurAB return True.
Return False.

Try Problem