Skip to content

1771. Maximize Palindrome Length From Subsequences 👍

  • 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
23
24
25
26
27
class Solution {
 public:
  int longestPalindrome(string word1, string word2) {
    const string& s = word1 + word2;
    const int n = s.length();
    int ans = 0;
    // 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];
          if (i < word1.length() && j >= word1.length())
            ans = max(ans, dp[i][j]);
        } else {
          dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
        }
      }

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
  public int longestPalindrome(String word1, String word2) {
    final String s = word1 + word2;
    final int n = s.length();
    int ans = 0;
    // 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];
          if (i < word1.length() && j >= word1.length())
            ans = Math.max(ans, dp[i][j]);
        } else {
          dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
        }
      }

    return ans;
  }
}