### vintage_Petr_Mitrichev's blog

By vintage_Petr_Mitrichev, history, 19 months ago,

TLE SOL

the first solution which gets ac , also recur for all the four case , and my 2nd solution also recur for all four cases .

But why i am getting tle at TC 6 , is there something i am missing , or something which is increasing the time complexity of 2nd sol.

someone please tell the mistake .

• 0

 » 19 months ago, # |   0 Your logic is not well explained. So I am not gonna read your code. But I will look at the base cases in recursion if I were you.
•  » » 19 months ago, # ^ | ← Rev. 2 →   0 what i am doing is if strings are same i am returning true , else if they are not . i divide both string into two parts , lets say s1 , s2 , s3 , s4 . now i am checking all 4 cases i.e case 1 : (s1 , s3) & (s2 , s4) leftleft rightrightcase 2 : (s1 , s4 ) & (s2 , s3) leftright rightleftam i clear .
 » 19 months ago, # |   0 Replace the following statements  for(ll i = i1 ; i<=j1 ; ++i) { left = left + s1[i] ; } for(ll i = i2 ; i<=j2 ; ++i) { right=right+s2[i] ; } with the following  for(ll i = i1 ; i<=j1 ; ++i) { left += s1[i]; } for(ll i = i2 ; i<=j2 ; ++i) { right += s2[i]; } and check if this change fixes the problem. The second code should just append s1[i] and s2[i] to the end of left and right strings in each iteration, respectively. The complexity of this operation in each iteration should be $O(1)$, and the complexity of both loops should be $O(n)$. On the other hand, the first code without compiler optimization should implicitly create a hidden string object that holds the result of appending the character s1[i] or s2[i] to the end of left or right string, respectively. Then, the hidden string object is copied back to the original string. The complexity of this operation in each iteration should be $O(n)$, and the complexity of both loops should be $O(n^2)$.
•  » » 19 months ago, # ^ |   0 ok .. so the string appendation is creating problem ... in first code string is appended from the place it left while i was doing everytime from start.. thaks .. i will modify it .
•  » » » 19 months ago, # ^ |   0 This is my guess.
•  » » » » 19 months ago, # ^ |   0 i think u r ri8 , u can see that my sol and ac sol. did the same , check all four cases , just appending is optimized .