Skip to content

516. Longest Palindromic Subsequence 👍

Approach 1: Top-down

  • Time: $O(n^2)$
  • Space: $O(n^2)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
 public:
  int longestPalindromeSubseq(string s) {
    const int n = s.length();
    vector<vector<int>> mem(n, vector<int>(n));
    return lps(s, 0, n - 1, mem);
  }

 private:
  // Returns the length of LPS(s[i..j]).
  int lps(const string& s, int i, int j, vector<vector<int>>& mem) {
    if (i > j)
      return 0;
    if (i == j)
      return 1;
    if (mem[i][j] > 0)
      return mem[i][j];
    if (s[i] == s[j])
      return mem[i][j] = 2 + lps(s, i + 1, j - 1, mem);
    return mem[i][j] = max(lps(s, i + 1, j, mem), lps(s, i, j - 1, mem));
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
  public int longestPalindromeSubseq(String s) {
    final int n = s.length();
    int[][] mem = new int[n][n];
    return lps(s, 0, n - 1, mem);
  }

  // Returns the length of LPS(s[i..j]).
  private int lps(String s, int i, int j, int[][] mem) {
    if (i > j)
      return 0;
    if (i == j)
      return 1;
    if (mem[i][j] > 0)
      return mem[i][j];
    if (s.charAt(i) == s.charAt(j))
      return mem[i][j] = 2 + lps(s, i + 1, j - 1, mem);
    return mem[i][j] = Math.max(lps(s, i + 1, j, mem), lps(s, i, j - 1, mem));
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
  def longestPalindromeSubseq(self, s: str) -> int:
    @functools.lru_cache(None)
    def dp(i: int, j: int) -> int:
      """Returns the length of LPS(s[i..j])."""
      if i > j:
        return 0
      if i == j:
        return 1
      if s[i] == s[j]:
        return 2 + dp(i + 1, j - 1)
      return max(dp(i + 1, j), dp(i, j - 1))

    return dp(0, len(s) - 1)

Approach 2: Bottom-up

  • Time: $O(n^2)$
  • Space: $O(n^2)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
 public:
  int longestPalindromeSubseq(string s) {
    const int n = s.length();
    // dp[i][j] := the length of LPS(s[i..j])
    vector<vector<int>> dp(n, vector<int>(n));

    for (int i = 0; i < n; ++i)
      dp[i][i] = 1;

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

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
  public int longestPalindromeSubseq(String s) {
    final int n = s.length();
    // dp[i][j] := the length of LPS(s[i..j])
    int[][] dp = new int[n][n];

    for (int i = 0; i < n; ++i)
      dp[i][i] = 1;

    for (int d = 1; d < n; ++d)
      for (int i = 0; i + d < n; ++i) {
        final int j = i + d;
        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];
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution:
  def longestPalindromeSubseq(self, s: str) -> int:
    n = len(s)
    # dp[i][j] := the length of LPS(s[i..j])
    dp = [[0] * n for _ in range(n)]

    for i in range(n):
      dp[i][i] = 1

    for d in range(1, n):
      for i in range(n - d):
        j = i + d
        if s[i] == s[j]:
          dp[i][j] = 2 + dp[i + 1][j - 1]
        else:
          dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])

    return dp[0][n - 1]