Maximize Palindrome Length From Subsequences — Solution
Maximize Palindrome Length From Subsequences solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Maximize Palindrome Length From Subsequences is a hard coding problem on strings and dynamic programming, asked in Amazon and Google interviews.
- Difficulty: Hard
- Topics: Strings, Dynamic Programming
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given two strings word1 and word2. Build a string as follows: choose a non-empty subsequence sub1 of word1 and a non-empty subsequence sub2 of word2, then concatenate them as sub1 + sub2.
Return the length of the longest palindrome that can be built this way. If no palindrome can be built, return 0.
A subsequence keeps the original order of the characters it uses but may skip any of them; a palindrome reads the same forwards and backwards.
Example 1
Input: word1 = "code", word2 = "kairo"
Output: 3
Explanation: Take `"od"` from `word1` and `"o"` from `word2` to get `"odo"`. The only letter both words share is `o`.
Example 2
Input: word1 = "abc", word2 = "cba"
Output: 6
Explanation: Use both words whole: `"abccba"`.
Example 3
Input: word1 = "aa", word2 = "bb"
Output: 0
Explanation: A palindrome would need its first character (from `word1`) to equal its last (from `word2`).
Constraints
1 <= word1.length, word2.length <= 1000word1 and word2 consist of lowercase English letters
Hints for Maximize Palindrome Length From Subsequences
Hint 1
Join the words:
s = word1 + word2. Any built string is a subsequence ofsthat uses at least one character on each side of the seam.Hint 2
In a palindrome the first and last characters match. Here the first comes from
word1and the last fromword2— so the outermost matched pair must straddle the seam.Hint 3
Compute the longest palindromic subsequence table
dp[i][j]ofs. Whenevers[i] == s[j]withiinword1andjinword2,dp[i][j] = dp[i+1][j-1] + 2is a candidate; take the maximum.
How to solve Maximize Palindrome Length From Subsequences
A palindrome built from sub1 + sub2 is a palindromic subsequence of s = word1 + word2 whose first character lies in word1 and whose last lies in word2 — and those two characters are equal. So run the standard longest-palindromic-subsequence DP on s and only accept answers whose outer pair crosses the seam.
Approach
- Let
s = word1 + word2andn1 = len(word1). - Fill
dp[i][j], the longest palindromic subsequence ofs[i..j], forifrom the end down andjupward:dp[i][i] = 1; ifs[i] == s[j]thendp[i][j] = dp[i+1][j-1] + 2, elsemax(dp[i+1][j], dp[i][j-1]). - Whenever
s[i] == s[j]withi < n1 <= j, update the answer withdp[i][j]. - Return the answer (0 if no such pair exists).
Why it works
If a valid palindrome exists, its outermost characters are equal, sit at some i < n1 <= j, and the inside is a palindromic subsequence of s[i+1..j-1], so its length is at most dp[i+1][j-1] + 2. Conversely, for any such equal pair, the pair plus a longest palindromic subsequence of the inside is a valid build — the outer characters guarantee both parts are non-empty, and the inside may use either word freely. So the maximum over straddling equal pairs is exactly the answer.
Complexity
- Time —
O((m + n)^2) - Space —
O((m + n)^2)
Pitfalls
- Taking the longest palindromic subsequence of
soverall is wrong — it may lie entirely inside one word. - Only pairs with
s[i] == s[j]may be the outer pair; amax(...)entry is not anchored atiandj. - If no letter occurs in both words, the answer is 0.
Reference solution
Python
def longestPalindrome(word1: str, word2: str) -> int:
s = word1 + word2
n, n1 = len(s), len(word1)
dp = [[0] * n for _ in range(n)]
best = 0
for i in range(n - 1, -1, -1):
dp[i][i] = 1
for j in range(i + 1, n):
if s[i] == s[j]:
dp[i][j] = dp[i + 1][j - 1] + 2
if i < n1 <= j and dp[i][j] > best:
best = dp[i][j]
else:
dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
return bestJava
public static int longestPalindrome(String word1, String word2) {
String s = word1 + word2;
int n = s.length(), n1 = word1.length();
int[][] dp = new int[n][n];
int best = 0;
for (int i = n - 1; i >= 0; i--) {
dp[i][i] = 1;
for (int j = i + 1; j < n; j++) {
if (s.charAt(i) == s.charAt(j)) {
dp[i][j] = dp[i + 1][j - 1] + 2;
if (i < n1 && j >= n1 && dp[i][j] > best) best = dp[i][j];
} else {
dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
}
}
}
return best;
}C++
int longestPalindrome(string word1, string word2) {
string s = word1 + word2;
int n = s.size(), n1 = word1.size();
vector<vector<int>> dp(n, vector<int>(n, 0));
int best = 0;
for (int i = n - 1; i >= 0; i--) {
dp[i][i] = 1;
for (int j = i + 1; j < n; j++) {
if (s[i] == s[j]) {
dp[i][j] = dp[i + 1][j - 1] + 2;
if (i < n1 && j >= n1 && dp[i][j] > best) best = dp[i][j];
} else {
dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
}
}
}
return best;
}JavaScript
var longestPalindrome = function(word1, word2) {
var s = word1 + word2, n = s.length, n1 = word1.length;
var dp = [];
for (var i = 0; i < n; i++) dp.push(new Array(n).fill(0));
var best = 0;
for (var i = n - 1; i >= 0; i--) {
dp[i][i] = 1;
for (var j = i + 1; j < n; j++) {
if (s[i] === s[j]) {
dp[i][j] = dp[i + 1][j - 1] + 2;
if (i < n1 && j >= n1 && dp[i][j] > best) best = dp[i][j];
} else {
dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
}
}
}
return best;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Dynamic Programming