<https://codeshare.io/2EbP7O>

# announcements

[warriorprincess]

https://codeshare.io/2EbP7O

[Andreas Sinz]

which execution time limit?

[warriorprincess]

hey its a competitive coding practice question from leetcode...

[warriorprincess]

they have an execution time limit in place for their large data sets

[warriorprincess]

to make sure the code is fast enough

[Andreas Sinz]

well the only thing you can do is compare the string directly inside isPalindrome instead of "converting" it into a CharArray, but there is not much more performance to get in the way you do it

[warriorprincess]

makes sense. the 'conversion' is of order N I am assuming?

[Andreas Sinz]

what do you mean with order N? O(N)?

[warriorprincess]

yes O(N)

[warriorprincess]

gotcha. so I have apparently increased the worst case complexity from O(N^2) to O(N^3)...

[warriorprincess]

thanks a lot!

[Andreas Sinz]

yes, toCharArray() copies every character one by one and because you do it twice + you reverse it, you are iterating over the string 3 times

[Andreas Sinz]

+ the comparsion iterates too over the whole array

[petersommerhoff]

Normally when you run into a timeout on challenges like that, it's because you need a different algorithm with a better runtime. For this problem, there's a DP approach: https://www.geeksforgeeks.org/longest-palindrome-substring-set-1/

[warriorprincess]

@Andreas Sinz Got it.

[warriorprincess]

@petersommerhoff Yup but in this case somehow I couldn't think of a faster solution...clearly I was wrong!

[warriorprincess]

thanks a lot for the link I'm studying it right now 🙂

[petersommerhoff]

@warriorprincess Didn't say it's easy, it's actually the hardest part simple smile

[warriorprincess]

@petersommerhoff yup DP problems are usually difficult for me

[petersommerhoff]

Not just for you but that just means it's good to practice