how to find longest palindromic subsequence?

by

This can be solved in O(n^2) using dynamic programming. Basically, the problem is about building the longest palindromic subsequence in x[i...j] using the longest subsequence for x[i+1...j], x[i,...j-1] and x[i+1,...,j-1] (if first and last letters are the same).

Firstly, the empty string and a single character string is trivially a palindrome.
Notice that for a substring x[i,...,j], if x[i]==x[j], we can say that the length of the longest palindrome is the longest palindrome over x[i+1,...,j-1]+2. If they don’t match, the longest palindrome is the maximum of that of x[i+1,...,j] and y[i,...,j-1].

This gives us the function:

longest(i,j)= j-i+1 if j-i<=0,
              2+longest(i+1,j-1) if x[i]==x[j]
              max(longest(i+1,j),longest(i,j-1)) otherwise

You can simply implement a memoized version of that function, or code a table of longest[i][j] bottom up.

This gives you only the length of the longest subsequence, not the actual subsequence itself. But it can easily be extended to do that as well.

More Related Contents:

  1. How to determine the longest increasing subsequence using dynamic programming?
  2. Subset Sum algorithm
  3. Write a function that returns the longest palindrome in a given string
  4. What is dynamic programming? [closed]
  5. Getting the submatrix with maximum sum?
  6. Box stacking problem
  7. How to split a string into words. Ex: “stringintowords” -> “String Into Words”?
  8. How to count integers between large A and B with a certain property?
  9. How to understand the dynamic programming solution in linear partitioning?
  10. Maximum Contiguous Subsequence Sum of At Least Length L
  11. 3-PARTITION problem
  12. Algorithm for Additive Color Mixing for RGB Values
  13. Algorithm to generate all possible permutations of a list?
  14. Fast permutation -> number -> permutation mapping algorithms
  15. Algorithm to detect intersection of two rectangles?
  16. An efficient compression algorithm for short text strings [closed]
  17. Generating the partitions of a number
  18. How to detect the BPM of a song in php [closed]
  19. Find the shortest path in a graph which visits certain nodes
  20. Algorithm to separate items of the same type
  21. how to calculate binary search complexity
  22. Combined area of overlapping circles
  23. Quick Sort Vs Merge Sort [duplicate]
  24. Algorithm to find the maximum sum in a sequence of overlapping intervals
  25. “Rounding” colour values to the nearest of a small set of colours
  26. Color gradient algorithm
  27. Unbiased random number generator using a biased one
  28. Why is vector array doubled?
  29. maximum subarray of an array with integers [duplicate]
  30. Can brute force algorithms scale?

Leave a Comment