_WATerror_AK's blog

Getting TLE in Question on Longest palindrome substring.
By _WATerror_AK, history, 3 years ago, In English

Can anyone help me out with my code to optimise this code.

Question Link-Question Link

Submission Link-Submission

  • Vote: I like it
  • -9
  • Vote: I do not like it

Comments Comments (6)
| Write comment?
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

can you provide the submission link, it is difficult to read.

→ Reply
»
3 years ago, # |
← Rev. 7   Vote: I like it 0 Vote: I do not like it

The maximum length of the input string is $$$1000$$$. You can use a brute-force algorithm to find the answer. Note that threre are $$$1, 2, 3, \ldots, N$$$ Substrings with lengths $$$N, N-1, N-2, \ldots, 1$$$, respectively. Start with Substring length $$$k = N$$$. If one of the $$$N-k+1$$$ Substrings with length $$$k$$$ is palindrome, then return it as the answer. Otherwise, decrement $$$k$$$ and repeat the previous step. If no palindrome Substring is found down to $$$k = 2$$$, then return any 1-letter Substring as the answer.

The following is my Kotlin implementation of the brute-force algorithm if you are interested.

Kotlin
→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In the recursive function, you are passing the string as pass by value. So if you pass it by value, for every call, the string is copied and adds an additional O(n) complexity.

→ Reply