Longest Palindrome After Substring Concatenation I
MedPrompt
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 <= 30sandtconsist of lowercase English letters.
Approaches
2 approaches with complexity analysis and trade-offs.
This approach exhaustively checks every possible pair of substrings from s and t. For each pair, it concatenates them and checks if the resulting string is a palindrome, keeping track of the maximum length found. This method is straightforward but computationally intensive.
Algorithm
- Initialize a variable
maxLengthto 0. - Generate all substrings of
s, including the empty string. This can be done with two nested loops for the start and end indices. - For each substring of
s(sub_s), generate all substrings oft(sub_t), also including the empty string. - Concatenate the two substrings:
combined = sub_s + sub_t. - If the
combinedstring is not empty, check if it is a palindrome. - A helper function
isPalindrome(str)can be used, which checks ifstrreads the same forwards and backwards. - If
combinedis a palindrome, updatemaxLength = max(maxLength, combined.length()). - After checking all pairs of substrings, return
maxLength.
Walkthrough
The algorithm iterates through all possible start and end indices to generate every substring of s, including the empty string. For each substring of s, it does the same for string t, generating all its substrings. The two substrings, sub_s and sub_t, are then concatenated. A helper function, isPalindrome, checks if this new string is a palindrome by comparing characters from both ends moving inwards. If it is a palindrome, its length is compared with the current maximum length, and the maximum is updated if necessary. This process naturally covers all three scenarios: a palindrome formed from a substring of s only (when sub_t is empty), from t only (when sub_s is empty), and from non-empty substrings of both s and t.
class Solution { private boolean isPalindrome(String str) { int left = 0; int right = str.length() - 1; while (left < right) { if (str.charAt(left) != str.charAt(right)) { return false; } left++; right--; } return true; } public int longestPalindrome(String s, String t) { int n = s.length(); int m = t.length(); int maxLength = 0; // Iterate through all substrings of s (including empty) for (int i = 0; i <= n; i++) { for (int j = i; j <= n; j++) { String sub_s = s.substring(i, j); // Iterate through all substrings of t (including empty) for (int k = 0; k <= m; k++) { for (int l = k; l <= m; l++) { String sub_t = t.substring(k, l); String combined = sub_s + sub_t; if (combined.isEmpty()) { continue; } if (isPalindrome(combined)) { maxLength = Math.max(maxLength, combined.length()); } } } } } return maxLength; }}Complexity
Time
O(N² * M² * (N + M)), where N and M are the lengths of `s` and `t`. There are O(N²) substrings for `s` and O(M²) for `t`. For each of the O(N² * M²) pairs, concatenation takes O(N+M) and the palindrome check also takes O(N+M).
Space
O(N + M), where N and M are the lengths of `s` and `t`. This space is used to store the concatenated string.
Trade-offs
Pros
Simple to understand and implement.
Guaranteed to be correct as it explores the entire search space.
Cons
The time complexity is very high due to the nested loops, making it impractical for larger string lengths.
It repeatedly performs substring creation and concatenation, which can be inefficient.
This optimized approach analyzes the structural properties of the palindrome formed by concatenating substrings. A palindrome P = sub_s + sub_t implies a specific relationship between sub_s and reverse(sub_t). By identifying common parts between s and the reverse of t, and extending them with pre-calculated palindromic substrings, we can find the longest palindrome much more efficiently.
Algorithm
- First, handle the base cases where the palindrome lies entirely within
sort. Find the longest palindromic substring in each and initializemaxLength. - The core idea for combined palindromes
sub_s + sub_tis thatsub_smust align withreverse(sub_t). Letrev_t = reverse(t). - We look for a common substring
Cbetweensandrev_t. The resulting palindrome will have the structureC + P + reverse(C), wherePis another palindrome. - Precompute all palindromic substrings for
sandrev_tusing a 2D DP table (e.g.,isPal[i][j]). This takesO(N² + M²). - From the
isPaltables, computelongestPalFrom[i], the length of the longest palindrome starting at indexifor bothsandrev_t. - Use another DP table to find lengths of all common substrings between
sandrev_t.dp[i][j]will store the length of the common substring ending ats[i-1]andrev_t[j-1]. - Iterate through the common substring DP table. For each common substring
Cof lengthk = dp[i][j]:- Consider the case where
sub_s = C + P_sandreverse(sub_t) = C. The total length is2*k + longestPalFrom[i]. UpdatemaxLength. - Consider the case where
sub_s = Candreverse(sub_t) = C + P_t. The total length is2*k + longestPalFrom[j](forrev_t). UpdatemaxLength.
- Consider the case where
- The even-length case (where the middle palindrome
Pis empty) is implicitly handled aslongestPalFromcan be 0. - Return the final
maxLength.
Walkthrough
If sub_s + sub_t is a palindrome, it must be equal to its reverse, which is reverse(sub_t) + reverse(sub_s). This structural property allows for a more targeted search. Let s1 = sub_s and s2 = reverse(sub_t). The combined string s1 + reverse(s2) must be a palindrome. This happens if:
s1ands2are identical (forms an even-length palindrome).- One is a prefix of the other, and the remaining part of the longer string is a palindrome.
This structure can be exploited using dynamic programming. We find common substrings between s and rev_t = reverse(t). Each common substring is a candidate for s1 or s2. We then check if this common part can be extended by a palindrome from s or t to form a larger palindrome.
class Solution { public int longestPalindrome(String s, String t) { int n = s.length(); int m = t.length(); int ans = 0; // 1. Palindromes entirely within s or t boolean[][] isPalS = computePalindromeDP(s); for (int i = 0; i < n; i++) { for (int j = i; j < n; j++) { if (isPalS[i][j]) { ans = Math.max(ans, j - i + 1); } } } boolean[][] isPalT = computePalindromeDP(t); for (int i = 0; i < m; i++) { for (int j = i; j < m; j++) { if (isPalT[i][j]) { ans = Math.max(ans, j - i + 1); } } } // 2. Combined palindromes String revT = new StringBuilder(t).reverse().toString(); boolean[][] isPalRevT = computePalindromeDP(revT); int[] longestPalFromS = getLongestPalFrom(s, isPalS); int[] longestPalFromRevT = getLongestPalFrom(revT, isPalRevT); int[][] dp = new int[n + 1][m + 1]; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { if (s.charAt(i - 1) == revT.charAt(j - 1)) { dp[i][j] = dp[i - 1][j - 1] + 1; int k = dp[i][j]; // Case: s part is longer (sub_s = common + palindrome) ans = Math.max(ans, 2 * k + longestPalFromS[i]); // Case: t part is longer (reverse(sub_t) = common + palindrome) ans = Math.max(ans, 2 * k + longestPalFromRevT[j]); } } } return ans; } private boolean[][] computePalindromeDP(String str) { int n = str.length(); boolean[][] dp = new boolean[n][n]; for (int i = 0; i < n; i++) dp[i][i] = true; for (int len = 2; len <= n; len++) { for (int i = 0; i <= n - len; i++) { int j = i + len - 1; if (str.charAt(i) == str.charAt(j)) { dp[i][j] = (len == 2) || dp[i + 1][j - 1]; } } } return dp; } private int[] getLongestPalFrom(String s, boolean[][] isPal) { int n = s.length(); int[] longest = new int[n + 1]; // longest[n] = 0 for (int i = n - 1; i >= 0; i--) { for (int j = i; j < n; j++) { if (isPal[i][j]) { longest[i] = Math.max(longest[i], j - i + 1); } } } return longest; }}Complexity
Time
O(N² + M²). The main components are computing palindrome information for `s` and `t` (O(N² + M²)) and filling the common substring DP table (O(N*M)).
Space
O(N² + M²), for storing the DP tables for palindrome checks and the common substring table.
Trade-offs
Pros
Highly efficient with a much lower polynomial time complexity.
Suitable for larger constraints where the brute-force approach would time out.
Cons
The implementation is significantly more complex than the brute-force approach.
It requires more space to store multiple DP tables.
Solutions
Solution
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; }}class Solution {public: int longestPalindrome(string s, string t) { int m = s.size(), n = t.size(); ranges ::reverse(t); vector<int> g1 = calc(s), g2 = calc(t); int ans = max(ranges ::max(g1), ranges ::max(g2)); vector<vector<int>> f(m + 1, vector<int>(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 = max(ans, f[i][j] * 2 + (i < m ? g1[i] : 0)); ans = max(ans, f[i][j] * 2 + (j < n ? g2[j] : 0)); } } } return ans; } private: void expand(const string &s, vector<int> &g, int l, int r) { while (l >= 0 && r < s.size() && s[l] == s[r]) { g[l] = max(g[l], r - l + 1); --l; ++r; } } vector<int> calc(const string &s) { int n = s.size(); vector<int> g(n, 0); for (int i = 0; i < n; ++i) { expand(s, g, i, i); expand(s, g, i, i + 1); } return g; }};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 ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.