516. Longest Palindromic Subsequence

• Visit Leetcode problem

Problem

Given a string s, find the longest palindromic subsequence's length in s.
A subsequence is a sequence that can be derived from another sequence by deleting 
some or no elements without changing the order of the remaining elements.


Example 1:
Input: s = "bbbab"
Output: 4
Explanation: One possible longest palindromic subsequence is "bbbb".

Example 2:
Input: s = "cbbd"
Output: 2
Explanation: One possible longest palindromic subsequence is "bb".
 
Constraints:
1 <= s.length <= 1000
s consists only of lowercase English letters.

Approach

Tương tự như các bài LC #72, #583
Gọi dfs(i,j) là longest palindromic subsequence của chuỗi s[i..j]
Ta tiến hành cho i, j chạy lần lượt từ đầu mảng và cuối chuỗi, tiến dần đến giữa chuỗi
Ta có công thức:

• Nếu s[i] = s[j] thì ta cộng thêm +2 (vì có 2 kí tự bằng giống nhau) vào kết quả và move pointer i, j xích lại gần tâm.
  dfs(i,j) = 2 + dfs(i+1, j-1)
• Nếu s[i] != s[j]. Ta tiến hành xoá kí tự i hoặc xoá kí tự j, sau đó move 1 trong con trỏ tới giữa tâm chuỗi.
  dfs(i,j) = max(dfs(i+1,j), dfs(i,j+1))
• Ngoài ra xử lí các case đặc biệt như i == j thì chỉ +1 vào kết quả, hoặc i>j thì +0 vào kết quả

  Implementation

  1. Recursion + memorization

  class Solution {
    private String s;
    private Map<String, Integer> memo;
  
    public int longestPalindromeSubseq(String s) {
        this.s = s;
        memo = new HashMap<>();
  
        return dfs(0, s.length() - 1);    
    }
  
    private int dfs(int i, int j) {
        if (i == j) return 1;
        if (i > j) return 0;
  
        String key = i + "_" + j;
        if (memo.containsKey(key)) {
            return memo.get(key);
        }
  
        int ans = 0;
        if (s.charAt(i) == s.charAt(j)) {
            ans = 2 + dfs(i+1, j-1);
        } else {
            ans = Math.max(dfs(i+1, j), // delete character i
                    dfs(i, j-1)); // delete character j
        }
  
        memo.put(key, ans);
        return ans;
    }
  }
  

Dynamic programming

class Solution {
    public int longestPalindromeSubseq(String s) {
        int n = s.length();
        int[][] dp = new int[n][n];

        for (int i = n-1; i >= 0; i--) {
            dp[i][i] = 1;
            for (int j = i+1; j < n; j++) {
                if (s.charAt(i) == s.charAt(j)) {
                    dp[i][j] = 2 + dp[i+1][j-1];
                } else {
                    dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1]);
                }
            }
        }

        return dp[0][n-1];
    }
}