Skip to content

1682. Longest Palindromic Subsequence II 👍

Approach 1: Top-down (TLE)

  • Time: $O(26n^2)$
  • Space: $O(26n^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<vector<int>>> mem(n, vector<vector<int>>(n, vector<int>(27)));
    return lps(s, 0, n - 1, 26, mem);
  }

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

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

  // Returns the length of LPS(s[i..j]), where the previous letter is ('a' + k).
  private int lps(final String s, int i, int j, int k, int[][][] mem) {
    if (i >= j)
      return 0;
    if (mem[i][j][k] > 0)
      return mem[i][j][k];
    if (s.charAt(i) == s.charAt(j) && s.charAt(i) != (char) (k + 'a'))
      return mem[i][j][k] = lps(s, i + 1, j - 1, s.charAt(i) - 'a', mem) + 2;
    return mem[i][j][k] = Math.max(lps(s, i + 1, j, k, mem), lps(s, i, j - 1, k, mem));
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution:
  def longestPalindromeSubseq(self, s: str) -> int:
    n = len(s)

    @functools.lru_cache(None)
    def dp(i: int, j: int, k: int) -> int:
      """
      Returns the length of LPS(s[i..j]), where the previous letter is
      ('a' + k).
      """
      if i >= j:
        return 0
      if s[i] == s[j] and s[i] != chr(ord('a') + k):
        return dp(i + 1, j - 1, ord(s[i]) - ord('a')) + 2
      return max(dp(i + 1, j, k), dp(i, j - 1, k))

    return dp(0, n - 1, 26)

Approach 2: Bottom-up

  • Time: $O(26n^2)$
  • Space: $O(26n^2)$
 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) {
    const int n = s.length();
    // dp[i][j][k] := the length of LPS(s[i..j]), where the previous letter is
    // ('a' + k).
    vector<vector<vector<int>>> dp(n, vector<vector<int>>(n, vector<int>(27)));

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

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

 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();
    // dp[i][j][k] := the length of LPS(s[i..j]), where the previous letter is
    // ('a' + k).
    int[][][] dp = new int[n][n][27];

    for (int d = 1; d < n; ++d)
      for (int i = 0; i + d < n; ++i)
        for (int k = 0; k <= 26; ++k) {
          final int j = i + d;
          if (s.charAt(i) == s.charAt(j) && s.charAt(i) != 'a' + k)
            dp[i][j][k] = dp[i + 1][j - 1][s.charAt(i) - 'a'] + 2;
          else
            dp[i][j][k] = Math.max(dp[i + 1][j][k], dp[i][j - 1][k]);
        }

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

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

    for d in range(1, n):
      for i in range(n - d):
        for k in range(27):
          j = i + d
          if s[i] == s[j] and s[i] != chr(ord('a') + k):
            dp[i][j][k] = dp[i + 1][j - 1][ord(s[i]) - ord('a')] + 2
          else:
            dp[i][j][k] = max(dp[i + 1][j][k], dp[i][j - 1][k])

    return dp[0][n - 1][26]