0
$\begingroup$

The problem that I'm trying to solve is: Given an array of length N, I want to find the length of the longest palindrome in the given array. With palindrome, we refer to a word, phrase, or sequence that reads the same backwards as forwards.

For example, if we give as input "1234321789" the algorithm should return 7.

I want the algorithm to have the smallest possible time complexity and efficiency.

$\endgroup$
1
  • 2
    $\begingroup$ What is the best (most efficient) algorithm you have tried so far? What approaches have you already considered? We're not particularly looking for posts that are just the statement of an exercise-style task. We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. You might find this page helpful in improving your question. $\endgroup$
    – D.W.
    Feb 3, 2023 at 5:02

1 Answer 1

1
$\begingroup$

First, take a look at https://www.geeksforgeeks.org/length-of-longest-palindrome-substring/ This might answer your question completely.

This will give you $O(n^2)$ time and $O(n)$ space complexity.

Now here is another trick that I think will work. We already know to find the longest common subsequence given two strings, right? It is a very common algorithm that uses dynamic programming. Let's call that method $LCS$

Now given your array or string, call it $s$ and compute $reverse(s) = s'$

Now compute $LCS(s,s')$. The LCS of both strings is the longest palindrome.

Note that this method will work only if we are looking for substrings and not subsequences. ABCAB reversed is BACBA, and while ACA is a palindrome, ACB is also the longest LCSs and not a palindrome. But Neither ABCAB nor BACBA contains ACA or ACB. This method will output any of the letters A, B, or C as a solution (since ABCAB doesn't contain palindromes of length $\geq 2$)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.