Is s1=s[j--]+s1 string operation is time costly in C++

Revision en1, by rajkumar62506, 2020-07-04 07:36:16

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?

sol having TLE.

Accepted sol.

Both sols only differ in way I calculated s2.

Tags #string, #palindrome, #tle


  Rev. Lang. By When Δ Comment
en3 English rajkumar62506 2020-07-04 08:27:56 85
en2 English rajkumar62506 2020-07-04 08:23:22 1240
en1 English rajkumar62506 2020-07-04 07:36:16 1475 Initial revision (published)