Leetcode Problem 1771. Maximize Palindrome Length From Subsequences

1771. Maximize Palindrome Length From Subsequences

Leetcode Solutions

Longest Palindromic Subsequence with Non-Empty Subsequences from Two Strings

  1. Concatenate word1 and word2 into a single string word.
  2. Initialize a 2D array dp with dimensions [n][n] where n is the length of word.
  3. Fill the dp array with the base case: dp[i][i] = 1 for all i.
  4. Use dynamic programming to fill in the dp array for all substrings of word.
  5. For each character in word1, find the corresponding character in word2 and use the dp array to find the LPS between these indices.
  6. Keep track of the maximum palindrome length that includes characters from both word1 and word2.
  7. Return the maximum palindrome length found.
UML Thumbnail

Enumerate Every Char Pair for Longest Palindrome

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...