Can someone be kind enough to share their approach for this problem?

All i could think of was brute force which gave me TLE (as expected).

I saw some successful submissions too but could not understand the approach.

Thanks

Can someone be kind enough to share their approach for this problem?

All i could think of was brute force which gave me TLE (as expected).

I saw some successful submissions too but could not understand the approach.

Thanks

From string b, keep pushing characters one by one to a new string (say x). Now at every step after pushing, just check if last characters of string x is equal to a. If it is then pop last characters equal to length of string a

This is essentially same as bruteforce approach in which you always remove the first subtring b found.

Complexity: O(|A|*|b|) Submission

1 Like

thanks. So, basically i got doomed by the inbuilt functionâ€™s linear complexity.