Break down a hard problem into reliable checkpoints, edge-case handling, and complexity trade-offs.
You are given two strings, word1 and word2. You want to construct a string in the following manner:
subsequence1 from word1.subsequence2 from word2.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 <= 1000word1 and word2 consist of lowercase English letters.Problem summary: 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.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Dynamic Programming
"cacb" "cbba"
"ab" "ab"
"aa" "bb"
longest-palindromic-subsequence)Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #1771: Maximize Palindrome Length From Subsequences
class Solution {
public int longestPalindrome(String word1, String word2) {
String s = word1 + word2;
int n = s.length();
int[][] f = new int[n][n];
for (int i = 0; i < n; ++i) {
f[i][i] = 1;
}
int ans = 0;
for (int i = n - 2; i >= 0; --i) {
for (int j = i + 1; j < n; ++j) {
if (s.charAt(i) == s.charAt(j)) {
f[i][j] = f[i + 1][j - 1] + 2;
if (i < word1.length() && j >= word1.length()) {
ans = Math.max(ans, f[i][j]);
}
} else {
f[i][j] = Math.max(f[i + 1][j], f[i][j - 1]);
}
}
}
return ans;
}
}
// Accepted solution for LeetCode #1771: Maximize Palindrome Length From Subsequences
func longestPalindrome(word1 string, word2 string) (ans int) {
s := word1 + word2
n := len(s)
f := make([][]int, n)
for i := range f {
f[i] = make([]int, n)
f[i][i] = 1
}
for i := n - 2; i >= 0; i-- {
for j := i + 1; j < n; j++ {
if s[i] == s[j] {
f[i][j] = f[i+1][j-1] + 2
if i < len(word1) && j >= len(word1) && ans < f[i][j] {
ans = f[i][j]
}
} else {
f[i][j] = max(f[i+1][j], f[i][j-1])
}
}
}
return ans
}
# Accepted solution for LeetCode #1771: Maximize Palindrome Length From Subsequences
class Solution:
def longestPalindrome(self, word1: str, word2: str) -> int:
s = word1 + word2
n = len(s)
f = [[0] * n for _ in range(n)]
for i in range(n):
f[i][i] = 1
ans = 0
for i in range(n - 2, -1, -1):
for j in range(i + 1, n):
if s[i] == s[j]:
f[i][j] = f[i + 1][j - 1] + 2
if i < len(word1) <= j:
ans = max(ans, f[i][j])
else:
f[i][j] = max(f[i + 1][j], f[i][j - 1])
return ans
// Accepted solution for LeetCode #1771: Maximize Palindrome Length From Subsequences
impl Solution {
pub fn longest_palindrome(word1: String, word2: String) -> i32 {
let s: Vec<char> = format!("{}{}", word1, word2).chars().collect();
let n = s.len();
let mut f = vec![vec![0; n]; n];
for i in 0..n {
f[i][i] = 1;
}
let mut ans = 0;
for i in (0..n - 1).rev() {
for j in i + 1..n {
if s[i] == s[j] {
f[i][j] = f[i + 1][j - 1] + 2;
if i < word1.len() && j >= word1.len() {
ans = ans.max(f[i][j]);
}
} else {
f[i][j] = f[i + 1][j].max(f[i][j - 1]);
}
}
}
ans
}
}
// Accepted solution for LeetCode #1771: Maximize Palindrome Length From Subsequences
function longestPalindrome(word1: string, word2: string): number {
const s = word1 + word2;
const n = s.length;
const f: number[][] = Array.from({ length: n }, () => Array.from({ length: n }, () => 0));
for (let i = 0; i < n; ++i) {
f[i][i] = 1;
}
let ans = 0;
for (let i = n - 2; ~i; --i) {
for (let j = i + 1; j < n; ++j) {
if (s[i] === s[j]) {
f[i][j] = f[i + 1][j - 1] + 2;
if (i < word1.length && j >= word1.length) {
ans = Math.max(ans, f[i][j]);
}
} else {
f[i][j] = Math.max(f[i + 1][j], f[i][j - 1]);
}
}
}
return ans;
}
Use this to step through a reusable interview workflow for this problem.
Pure recursion explores every possible choice at each step. With two choices per state (take or skip), the decision tree has 2ⁿ leaves. The recursion stack uses O(n) space. Many subproblems are recomputed exponentially many times.
Each cell in the DP table is computed exactly once from previously solved subproblems. The table dimensions determine both time and space. Look for the state variables — each unique combination of state values is one cell. Often a rolling array can reduce space by one dimension.
Review these before coding to avoid predictable interview regressions.
Wrong move: An incomplete state merges distinct subproblems and caches incorrect answers.
Usually fails on: Correctness breaks on cases that differ only in hidden state.
Fix: Define state so each unique subproblem maps to one DP cell.