Overlapping ABBA

Easy
0/40
Average time to solve is 10m
profile
Contributed by
65 upvotes
Asked in companies
AmazonVisaAccolite

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).
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2
ABA
BACFAB
Sample Output 1 :
False
True
Explanation for Sample Output 1 :
In the first test case, there are no two non-overlapping substrings, so “False” is printed.

In the second test case, there are two non-overlapping substrings (BACFAB), so “True” is printed.
Sample Input 2 :
2
ABBA
AXBYBXA
Sample Output 2 :
True
False
Hint

Check the first and last occurrences of the sub-string “AB” and “BA”.

Approaches (1)
Brute Force

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:-

 

  1. 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.
  2. 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).
  3. If LastOccurAB is not equal to - 1 and FirstOccurBA is not equal to |S| and LastOccurAB is greater than FirstOccurBA return True.
  4. If LastOccurBA is not equal to - 1 and FirstOccurAB is not equal to |S| and LastOccurBA is greater than FirstOccurAB return True.
  5. Return False.
Time Complexity

O(|S|), where |S| is the length of the string S.


 

We are iterating through every character in the string S once, so the Time complexity is O(|S|) when |S| is the length of the string S.

Space Complexity

O(1)

 

Constant Space is used.

Code Solution
(100% EXP penalty)
Overlapping ABBA
Full screen
Console