Is Longest Palindrome After Substring Concatenation I easy or hard?

The problem is generally classified as Medium difficulty. The brute force idea is straightforward, but reaching the optimal O(n^2) solution requires recognizing palindrome center expansion and combining it with dynamic programming for substring validation.

Longest Palindrome After Substring Concatenation I Python/Java solution

The typical implementation first builds a DP table for palindrome substrings and then iterates through possible centers using two pointers. The same logic translates directly across Python, Java, C++, Go, and TypeScript since it relies on simple array indexing and nested loops.

What is the best approach for Longest Palindrome After Substring Concatenation I?

The most efficient method enumerates palindrome centers and uses dynamic programming to precompute palindromic substrings. Center expansion checks how characters from both chosen substrings mirror each other, while the DP table instantly validates internal palindrome segments. This reduces repeated checks and achieves O(n^2) time complexity.

Is Longest Palindrome After Substring Concatenation I asked at Google/Amazon/Meta?

Problems involving palindrome expansion, substring concatenation, and dynamic programming frequently appear in interviews at companies like Google, Amazon, and Meta. Variants of longest palindrome and substring combination problems are common in technical screens.

What data structure is used in Longest Palindrome After Substring Concatenation I?

The core structure is a 2D dynamic programming table that records whether substrings are palindromes. The algorithm also relies on two-pointer expansion from palindrome centers to compare characters efficiently across concatenated substrings.

What is the time complexity of Longest Palindrome After Substring Concatenation I?

The optimal solution runs in O(n^2) time with O(n^2) space using center expansion combined with dynamic programming. Brute force enumeration of all substring pairs can reach O(n^4) time, which is too slow for typical constraints.

Description Hints 1 Solution Video 12:29

3503. Longest Palindrome After Substring Concatenation I

Q: How to solve Longest Palindrome After Substring Concatenation I in O(n^2)?

Precompute a DP table where dp[i][j] indicates whether substring i..j is a palindrome. Then enumerate possible palindrome centers and expand outward using two pointers, comparing characters from the two selected substrings. When expansion stops, use the DP table to verify whether the remaining internal section forms a palindrome.

Medium43.8% acceptance2 companies

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 <= 30
s and t consist of lowercase English letters.

Asked at 2 companies

Google Meta

Topics

Hints open one at a time

Hint 1

Brute force

12:29

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def longestPalindrome(self, s: str, t: str) -> int:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2Case 3Case 4

Input

"a"
"a"

Input

"abc"
"def"

Input

"b"
"aaaa"

Input

"abcde"
"ecdba"

Your code is saved on this device.Solution