Scale Engineer

Longest Palindrome After Substring Concatenation II

Hard
#3116Time: O(N² * M² * (N + M)). There are O(N²) substrings in `s` and O(M²) in `t`. For each pair, concatenation takes O(N+M) and the palindrome check takes O(N+M). This is computationally prohibitive.Space: O(N + M), where N and M are the lengths of `s` and `t`. This space is used to store the concatenated string.
Patterns
Two PointersDynamic Programming
Data structures
String

Prompt

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

Approaches

2 approaches with complexity analysis and trade-offs.

The most straightforward approach is to exhaustively check every possible palindrome that can be formed. We can iterate through all substrings of s and all substrings of t, concatenate them, and check if the resulting string is a palindrome. We keep track of the maximum length found.

Algorithm

  • Initialize maxLength to 0.
  • Generate all possible non-empty substrings of s. Let a substring be sub_s.
  • Generate all possible non-empty substrings of t. Let a substring be sub_t.
  • For each pair of (sub_s, sub_t):
    • Create the concatenated string newStr = sub_s + sub_t.
    • Check if newStr is a palindrome.
    • If it is, update maxLength = max(maxLength, newStr.length()).
  • Also consider cases where one of the substrings is empty. This means finding the longest palindromic substring within s and t individually and updating maxLength.
  • Return maxLength.

Walkthrough

This method involves a nested loop structure to generate all substrings and then test them.

  1. Generate Substrings: We use four nested loops to define the start and end indices for substrings from both s and t.
  2. Concatenate and Test: For each pair of substrings, sub_s and sub_t, we form a new string. A helper function is used to check if this new string is a palindrome. This check can be done by comparing the string with its reverse.
  3. Handle Empty Substrings: The problem allows for empty substrings. This is equivalent to finding the longest palindromic substring within s or t alone. This should be done as a base case.

Here is a conceptual code snippet for the core logic:

public int longestPalindrome(String s, String t) {    int n = s.length();    int m = t.length();    int maxLen = 0;     // Helper to find longest palindromic substring in a single string    // maxLen = Math.max(lps(s), lps(t));     for (int i = 0; i < n; i++) {        for (int j = i; j < n; j++) {            String sub_s = s.substring(i, j + 1);            for (int k = 0; k < m; k++) {                for (int l = k; l < m; l++) {                    String sub_t = t.substring(k, l + 1);                    String combined = sub_s + sub_t;                    if (isPalindrome(combined)) {                        maxLen = Math.max(maxLen, combined.length());                    }                }            }        }    }    return maxLen;} private boolean isPalindrome(String str) {    int left = 0, right = str.length() - 1;    while (left < right) {        if (str.charAt(left) != str.charAt(right)) {            return false;        }        left++;        right--;    }    return true;}

Complexity

Time

O(N² * M² * (N + M)). There are O(N²) substrings in `s` and O(M²) in `t`. For each pair, concatenation takes O(N+M) and the palindrome check takes O(N+M). This is computationally prohibitive.

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.

Cons

  • Extremely inefficient due to the large number of substring pairs.

  • The time complexity makes it infeasible for the given constraints.

Solutions

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.

← Previous

Previous problem

Next →

Next problem