[Coding Made Simple] Longest Palindromic Subsequence

Given a string, find longest palindromic subsequence in this string.

lps[start, end] = lps[start + 1, end - 1] + 2, if s.charAt(start) == s.charAt(end);

lps[start, end] = Math.max(lps[start + 1][end], lps[start][end - 1]), if s.charAt(start) != s.charAt(end).

Base case: start > end, lps = 0; start == end, lps = 1.

Based on the above formula, we can use either recursion or dynamic programming to solve this problem.

Recursive solution.

 1 public class LongestPalSubseq {
 2     public int getLenOfLPSRecursion(String s) {
 3         if(s == null) {
 4             return 0;
 5         }
 6         return recursiveHelper(s, 0, s.length() - 1);
 7     }
 8     private int recursiveHelper(String s, int start, int end) {
 9         if(start > end) {
10             return 0;
11         }
12         else if(start == end) {
13             return 1;
14         }
15         if(s.charAt(start) == s.charAt(end)) {
16             return 2 + recursiveHelper(s, start + 1, end - 1);
17         }
18         return Math.max(recursiveHelper(s, start + 1, end), recursiveHelper(s, start, end - 1));
19     }
20     public static void main(String[] args) {
21         String s1 = "agbdba", s2 = "", s3 = "a", s4 = "abcefegdba";
22         LongestPalSubseq test = new LongestPalSubseq();
23         System.out.println(test.getLenOfLPSRecursion(s1));
24         System.out.println(test.getLenOfLPSRecursion(s2));
25         System.out.println(test.getLenOfLPSRecursion(s3));
26         System.out.println(test.getLenOfLPSRecursion(s4));
27     }
28 }

Dynamic programming solution. T[i][j]: the length of longest palindromic subsequence in substring s[i....j].

 1 import java.util.ArrayList;
 2 
 3 public class LongestPalSubseq {
 4     private ArrayList<Character> palinSeq;
 5     public int getLenOfLpsDp(String s) {
 6         palinSeq = new ArrayList<Character>();
 7         if(s == null|| s.length() == 0) {
 8             return 0;
 9         }
10         int[][] T = new int[s.length()][s.length()];
11         for(int i = 0; i < T.length; i++) {
12             T[i][i] = 1;
13         }
14         for(int len = 2; len <= s.length(); len++) {
15             for(int i = 0; i <= s.length() - len; i++) {
16                 if(s.charAt(i) == s.charAt(i + len - 1)) {
17                     T[i][i + len - 1] = len >= 3 ? T[i + 1][i + len - 2] + 2 : 2;
18                 }
19                 else {
20                     T[i][i + len - 1] = Math.max(T[i + 1][i + len - 1], T[i][i + len - 2]);
21                 }
22             }
23         }
24         int start = 0, end = s.length() - 1;
25         while(start <= end) {
26             if(s.charAt(start) == s.charAt(end)) {
27                 palinSeq.add(s.charAt(start));
28                 start++;
29                 end--;
30             }
31             else{
32                 if(T[start + 1][end] > T[start][end - 1]) {
33                     start++;
34                 }
35                 else {
36                     end--;
37                 }
38             }
39         }
40         for(int i = T[0][s.length() - 1] / 2 - 1; i >= 0; i--) {
41             palinSeq.add(palinSeq.get(i));
42         }
43         return T[0][s.length() - 1];
44     }    
45 }