Break down a hard problem into reliable checkpoints, edge-case handling, and complexity trade-offs.
You are given two strings, s and t.
You can create a new string by selecting a substring from s (possibly empty) and a substring from t (possibly empty), then concatenating them in order.
Return the length of the longest palindrome that can be formed this way.
Example 1:
Input: s = "a", t = "a"
Output: 2
Explanation:
Concatenating "a" from s and "a" from t results in "aa", which is a palindrome of length 2.
Example 2:
Input: s = "abc", t = "def"
Output: 1
Explanation:
Since all characters are different, the longest palindrome is any single character, so the answer is 1.
Example 3:
Input: s = "b", t = "aaaa"
Output: 4
Explanation:
Selecting "aaaa" from t is the longest palindrome, so the answer is 4.
Example 4:
Input: s = "abcde", t = "ecdba"
Output: 5
Explanation:
Concatenating "abc" from s and "ba" from t results in "abcba", which is a palindrome of length 5.
Constraints:
1 <= s.length, t.length <= 1000s and t consist of lowercase English letters.Problem summary: You are given two strings, s and t. You can create a new string by selecting a substring from s (possibly empty) and a substring from t (possibly empty), then concatenating them in order. Return the length of the longest palindrome that can be formed this way.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Two Pointers · Dynamic Programming
"a" "a"
"abc" "def"
"b" "aaaa"
edit-distance)Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #3504: Longest Palindrome After Substring Concatenation II
class Solution {
public int longestPalindrome(String S, String T) {
char[] s = S.toCharArray();
char[] t = new StringBuilder(T).reverse().toString().toCharArray();
int m = s.length, n = t.length;
int[] g1 = calc(s), g2 = calc(t);
int ans = Math.max(Arrays.stream(g1).max().getAsInt(), Arrays.stream(g2).max().getAsInt());
int[][] f = new int[m + 1][n + 1];
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
if (s[i - 1] == t[j - 1]) {
f[i][j] = f[i - 1][j - 1] + 1;
ans = Math.max(ans, f[i][j] * 2 + (i < m ? g1[i] : 0));
ans = Math.max(ans, f[i][j] * 2 + (j < n ? g2[j] : 0));
}
}
}
return ans;
}
private void expand(char[] s, int[] g, int l, int r) {
while (l >= 0 && r < s.length && s[l] == s[r]) {
g[l] = Math.max(g[l], r - l + 1);
--l;
++r;
}
}
private int[] calc(char[] s) {
int n = s.length;
int[] g = new int[n];
for (int i = 0; i < n; ++i) {
expand(s, g, i, i);
expand(s, g, i, i + 1);
}
return g;
}
}
// Accepted solution for LeetCode #3504: Longest Palindrome After Substring Concatenation II
func longestPalindrome(s, t string) int {
m, n := len(s), len(t)
t = reverse(t)
g1, g2 := calc(s), calc(t)
ans := max(slices.Max(g1), slices.Max(g2))
f := make([][]int, m+1)
for i := range f {
f[i] = make([]int, n+1)
}
for i := 1; i <= m; i++ {
for j := 1; j <= n; j++ {
if s[i-1] == t[j-1] {
f[i][j] = f[i-1][j-1] + 1
a, b := 0, 0
if i < m {
a = g1[i]
}
if j < n {
b = g2[j]
}
ans = max(ans, f[i][j]*2+a)
ans = max(ans, f[i][j]*2+b)
}
}
}
return ans
}
func calc(s string) []int {
n, g := len(s), make([]int, len(s))
for i := 0; i < n; i++ {
expand(s, g, i, i)
expand(s, g, i, i+1)
}
return g
}
func expand(s string, g []int, l, r int) {
for l >= 0 && r < len(s) && s[l] == s[r] {
g[l] = max(g[l], r-l+1)
l, r = l-1, r+1
}
}
func reverse(s string) string {
r := []rune(s)
slices.Reverse(r)
return string(r)
}
# Accepted solution for LeetCode #3504: Longest Palindrome After Substring Concatenation II
class Solution:
def longestPalindrome(self, s: str, t: str) -> int:
def expand(s: str, g: List[int], l: int, r: int):
while l >= 0 and r < len(s) and s[l] == s[r]:
g[l] = max(g[l], r - l + 1)
l, r = l - 1, r + 1
def calc(s: str) -> List[int]:
n = len(s)
g = [0] * n
for i in range(n):
expand(s, g, i, i)
expand(s, g, i, i + 1)
return g
m, n = len(s), len(t)
t = t[::-1]
g1, g2 = calc(s), calc(t)
ans = max(*g1, *g2)
f = [[0] * (n + 1) for _ in range(m + 1)]
for i, a in enumerate(s, 1):
for j, b in enumerate(t, 1):
if a == b:
f[i][j] = f[i - 1][j - 1] + 1
ans = max(ans, f[i][j] * 2 + (0 if i >= m else g1[i]))
ans = max(ans, f[i][j] * 2 + (0 if j >= n else g2[j]))
return ans
// Accepted solution for LeetCode #3504: Longest Palindrome After Substring Concatenation II
// Rust example auto-generated from java reference.
// Replace the signature and local types with the exact LeetCode harness for this problem.
impl Solution {
pub fn rust_example() {
// Port the logic from the reference block below.
}
}
// Reference (java):
// // Accepted solution for LeetCode #3504: Longest Palindrome After Substring Concatenation II
// class Solution {
// public int longestPalindrome(String S, String T) {
// char[] s = S.toCharArray();
// char[] t = new StringBuilder(T).reverse().toString().toCharArray();
// int m = s.length, n = t.length;
// int[] g1 = calc(s), g2 = calc(t);
// int ans = Math.max(Arrays.stream(g1).max().getAsInt(), Arrays.stream(g2).max().getAsInt());
// int[][] f = new int[m + 1][n + 1];
// for (int i = 1; i <= m; ++i) {
// for (int j = 1; j <= n; ++j) {
// if (s[i - 1] == t[j - 1]) {
// f[i][j] = f[i - 1][j - 1] + 1;
// ans = Math.max(ans, f[i][j] * 2 + (i < m ? g1[i] : 0));
// ans = Math.max(ans, f[i][j] * 2 + (j < n ? g2[j] : 0));
// }
// }
// }
// return ans;
// }
//
// private void expand(char[] s, int[] g, int l, int r) {
// while (l >= 0 && r < s.length && s[l] == s[r]) {
// g[l] = Math.max(g[l], r - l + 1);
// --l;
// ++r;
// }
// }
//
// private int[] calc(char[] s) {
// int n = s.length;
// int[] g = new int[n];
// for (int i = 0; i < n; ++i) {
// expand(s, g, i, i);
// expand(s, g, i, i + 1);
// }
// return g;
// }
// }
// Accepted solution for LeetCode #3504: Longest Palindrome After Substring Concatenation II
function longestPalindrome(s: string, t: string): number {
function expand(s: string, g: number[], l: number, r: number): void {
while (l >= 0 && r < s.length && s[l] === s[r]) {
g[l] = Math.max(g[l], r - l + 1);
l--;
r++;
}
}
function calc(s: string): number[] {
const n = s.length;
const g: number[] = Array(n).fill(0);
for (let i = 0; i < n; i++) {
expand(s, g, i, i);
expand(s, g, i, i + 1);
}
return g;
}
const m = s.length,
n = t.length;
t = t.split('').reverse().join('');
const g1 = calc(s);
const g2 = calc(t);
let ans = Math.max(...g1, ...g2);
const f: number[][] = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));
for (let i = 1; i <= m; i++) {
for (let j = 1; j <= n; j++) {
if (s[i - 1] === t[j - 1]) {
f[i][j] = f[i - 1][j - 1] + 1;
ans = Math.max(ans, f[i][j] * 2 + (i >= m ? 0 : g1[i]));
ans = Math.max(ans, f[i][j] * 2 + (j >= n ? 0 : g2[j]));
}
}
}
return ans;
}
Use this to step through a reusable interview workflow for this problem.
Two nested loops check every pair of elements. The outer loop picks one element, the inner loop scans the rest. For n elements that is n × (n−1)/2 comparisons = O(n²). No extra memory — just two loop variables.
Each pointer traverses the array at most once. With two pointers moving inward (or both moving right), the total number of steps is bounded by n. Each comparison is O(1), giving O(n) overall. No auxiliary data structures are needed — just two index variables.
Review these before coding to avoid predictable interview regressions.
Wrong move: Advancing both pointers shrinks the search space too aggressively and skips candidates.
Usually fails on: A valid pair can be skipped when only one side should move.
Fix: Move exactly one pointer per decision branch based on invariant.
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.