Hello Coders, Suppose I have string s and I'm creating new string s1 by s1=s[j--]+s1 where j is initially (j=s.length()-1). Is this operation in C++ is time costly.
Because I was solving D2. Prefix-Suffix Palindrome (Hard version) problem.In this problem we are given string s,and we need to find string t,which satisfy given condition.
1)The length of t does not exceed the length of s.
2)t is a palindrome.
3)There exists two strings a and b (possibly empty), such that t=a+b ( "+" represents concatenation), and a is prefix of s while b is suffix of s.
I tried to solve it in following way,
1)string s1=s2="" and i=0,j=s.length()-1, now till s[i]==s[j],I added elements to s1 and s2; ie. s1+=s[i++],s2=s[j--]+s2;
2)after first step whatever string remains unused,I found longest prefix and suffix palindrome using manachers alg,and choosen max of them.
Now Main point is that when I submitted it was giving TLE on testcase 13. then I just tried to change s2=s[j--]+s2 by just only finding s1 and s2 will be obviously reverse of s1. And my code gets Accepted.
So my question is how can s2=s[j--]+s2 can be reason for TLE?
Both sols only differ in way I calculated s2.