1771. Maximize Palindrome Length From Subsequences LeetCode Solution
In this guide, you will get 1771. Maximize Palindrome Length From Subsequences LeetCode Solution with the best time and space complexity. The solution to Maximize Palindrome Length From Subsequences problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Maximize Palindrome Length From Subsequences
You are given two strings, word1 and word2. You want to construct a string in the following manner:
Choose some non-empty subsequence subsequence1 from word1.
Choose some non-empty subsequence subsequence2 from word2.
Concatenate the subsequences: subsequence1 + subsequence2, to make the string.
Return the length of the longest palindrome that can be constructed in the described manner. If no palindromes can be constructed, return 0.
A subsequence of a string s is a string that can be made by deleting some (possibly none) characters from s without changing the order of the remaining characters.
A palindrome is a string that reads the same forward as well as backward.
Example 1:
Input: word1 = “cacb”, word2 = “cbba”
Output: 5
Explanation: Choose “ab” from word1 and “cba” from word2 to make “abcba”, which is a palindrome.
Example 2:
Input: word1 = “ab”, word2 = “ab”
Output: 3
Explanation: Choose “ab” from word1 and “a” from word2 to make “aba”, which is a palindrome.
Example 3:
Input: word1 = “aa”, word2 = “bb”
Output: 0
Explanation: You cannot construct a palindrome from the described method, so return 0.
Constraints:
1 <= word1.length, word2.length <= 1000
word1 and word2 consist of lowercase English letters.
Complexity Analysis
Time Complexity: O(n^2)
Space Complexity: O(n^2)
1771. Maximize Palindrome Length From Subsequences LeetCode Solution in C++
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;
}
}; /* code provided by PROGIEZ */
1771. Maximize Palindrome Length From Subsequences LeetCode Solution in Java
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;
}
} // code provided by PROGIEZ
1771. Maximize Palindrome Length From Subsequences LeetCode Solution in Python
