<https codeshare io 2EbP7O> kotlinlang #announcements

warriorprincess

04/23/2018, 5:55 PM

Andreas Sinz

04/23/2018, 5:59 PM

which execution time limit?

warriorprincess

04/23/2018, 6:02 PM

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

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

to make sure the code is fast enough

Andreas Sinz

04/23/2018, 6:05 PM

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

04/23/2018, 6:06 PM

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

Andreas Sinz

04/23/2018, 6:07 PM

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

warriorprincess

04/23/2018, 6:07 PM

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

thanks a lot!

Andreas Sinz

04/23/2018, 6:10 PM

toCharArray()

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

+ the comparsion iterates too over the whole array

petersommerhoff

04/23/2018, 6:13 PM

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

04/23/2018, 6:20 PM

@Andreas Sinz Got it.

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

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

petersommerhoff

04/23/2018, 6:21 PM

@warriorprincess Didn't say it's easy, it's actually the hardest part 😒imple_smile:

warriorprincess

04/23/2018, 6:23 PM

@petersommerhoff yup DP problems are usually difficult for me

petersommerhoff

04/23/2018, 6:32 PM

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