CLSTRN - Coders Legacy Approach

stack
strings

#1

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

https://www.codechef.com/COLG2017/problems/CLSTRN

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


#2

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


#3

thanks. So, basically i got doomed by the inbuilt function’s linear complexity.