publicintlongestPalindromeSubseq(String s){ if (s == null || s.length() == 0) { return0; } int n = s.length(); return palSubseq(s, 0, n - 1); }

privateintpalSubseq(String s, int lo, int hi){ if (lo == hi) { return1; } if (lo > hi) { return0; } if (s.charAt(lo) == s.charAt(hi)) { return palSubseq(s, lo + 1, hi - 1) + 2; } else { return Math.max(palSubseq(s, lo + 1, hi), palSubseq(s, lo, hi - 1)); } }

Time: $O(2^N)$ in the worst case when $T(N) = 2T(N - 1)$. In the best case, it is $O(N)$. Space: $O(N)$

DP (memoization)

Based on the brute-force solution, we found repeated calculation. We can use memoization to optimize the time complexity.

publicintlongestPalindromeSubseq(String s){ if (s == null || s.length() == 0) { return0; } int n = s.length(); int[][] mem = newint[n][n]; // init for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { mem[i][j] = -1; } } return palSubseq(s, 0, s.length() - 1, mem); }

privateintpalSubseq(String s, int lo, int hi, int[][] mem){ if (lo == hi) { return1; } if (lo > hi) { return0; } if (s.charAt(lo) == s.charAt(hi)) { if (mem[lo + 1][hi - 1] == -1) { mem[lo + 1][hi - 1] = palSubseq(s, lo + 1, hi - 1, mem); } return mem[lo + 1][hi - 1] + 2; } else { if (mem[lo + 1][hi] == -1) { mem[lo + 1][hi] = palSubseq(s, lo + 1, hi, mem); } if (mem[lo][hi - 1] == -1) { mem[lo][hi - 1] = palSubseq(s, lo, hi - 1, mem); } return Math.max(mem[lo + 1][hi], mem[lo][hi - 1]); } }

Time: $O(N^2)$ Space: $O(N^2)$

DP (2D)

Define: We denote dp[i][j] as the longest palindromic subsequence’s length in the substring s(i, j).

Recurrence:

If s[i] == s[j], then dp[i][j] = dp[i + 1][j - 1] + 2.

Else, then dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]).

Initialization: Check out the base cases in the brute-force solution.

Note: Determining ranges of i and j would be easy if you pick a starting point in the graph to get some intuition. For example, in this case j starts from i + 1.