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.
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; }}Video 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.