# Longest Palindrome After Substring Concatenation II
**Difficulty:** HARD
[External](https://leetcode.com/problems/longest-palindrome-after-substring-concatenation-ii)
Canonical: https://scaleengineer.com/dsa/problems/longest-palindrome-after-substring-concatenation-ii
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers), [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** String
---
## Problem
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
## Brute-Force Enumeration of Substrings
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.
**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.
**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.
### Explanation
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:

```java
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;
}
```
### 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`.

## Dynamic Programming for Common Substrings
A more efficient approach recognizes the structure of the final palindrome. Any such palindrome `P` formed by `sub_s + sub_t` can be deconstructed into `L + M + reverse(L)`, where `M` is itself a palindrome (and can be empty). The parts `L` and `reverse(L)` must come from different strings, while `M` must be a substring of one of them, adjacent to its `L` part.

This structure means we are looking for a string `L` that is a substring of `s`, while `reverse(L)` is a substring of `t` (or vice-versa). This is equivalent to finding a common substring between `s` and `reverse(t)`. We can use dynamic programming to find all such common substrings and then, for each, find the longest possible central palindrome `M` to form the complete palindrome.
**Time:** O(N² + M²). Precomputing palindrome information for `s` and `t` takes O(N²) and O(M²) respectively. The DP table for common substrings is filled in O(N*M). The total complexity is the sum of these parts. · **Space:** O(N² + M²). The space is dominated by the tables for precomputing palindrome information (`isPalS`, `isPalT`) and the DP table for common substrings (`dp`), which is O(N*M).
**Pros:** Significantly more efficient than the brute-force approach.; Correctly solves the problem within the given time limits.; The approach is systematic and covers all possible palindrome constructions.
**Cons:** More complex to implement compared to the brute-force approach.; Requires significant auxiliary space for DP tables and precomputed palindrome information.
### Explanation
This approach can be broken down into several steps:

1.  **Handle Base Cases**: First, we find the longest palindrome that can be formed using a substring from only `s` or only `t`. This covers the cases where one of the selected substrings is empty.

2.  **Precompute Palindrome Lengths**: We need to quickly query the length of the longest palindrome starting or ending at any given index. We can precompute this information for both `s` and `t` in O(N²) and O(M²) time respectively.

    ```java
    // Helper to compute palindrome info. isPal[i][j] is true if s[i..j] is a palindrome.
    private boolean[][] computeIsPalindrome(String s) { ... }

    // Helper to get lengths of palindromes starting or ending at each index from the isPal table.
    private int[] getPalLengths(String s, boolean starts, boolean[][] isPal) { ... }
    ```

3.  **Find Common Substrings using DP**: We find common substrings between `s` and `reverse(t)`. Let `t_rev = reverse(t)`. We build a DP table where `dp[i][j]` stores the length of the longest common substring ending at `s[i-1]` and `t_rev[j-1]`.

4.  **Construct Palindromes and Find Max Length**: We iterate through the DP table. A non-zero `dp[i][j]` gives us a matching part `L`. We then check the two possible ways to form a larger palindrome:

    *   `L` from `s`, `M` from `s`, `reverse(L)` from `t`.
    *   `L` from `s`, `reverse(L)` from `t`, `M` from `t`.

We use our precomputed palindrome lengths to find the longest possible `M` in each case and update our maximum length.

```java
class Solution {
    public int longestPalindrome(String s, String t) {
        // Step 1: Base cases (palindrome entirely in s or t)
        int maxLen = 0;
        boolean[][] isPalS = computeIsPalindrome(s);
        boolean[][] isPalT = computeIsPalindrome(t);
        maxLen = Math.max(findLongestPal(s, isPalS), findLongestPal(t, isPalT));

        // Step 2: Precompute palindrome lengths
        int[] palLenSStarts = getPalLengths(s, true, isPalS);
        int[] palLenTEnds = getPalLengths(t, false, isPalT);

        // Step 3 & 4: Find common parts and combine
        String tRev = new StringBuilder(t).reverse().toString();
        int n = s.length(), m = t.length();
        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) == tRev.charAt(j - 1)) {
                    int lenL = dp[i - 1][j - 1] + 1;
                    dp[i][j] = lenL;

                    // Case A: sub_s = L+M, sub_t = reverse(L)
                    int lenM_s = (i < n) ? palLenSStarts[i] : 0;
                    maxLen = Math.max(maxLen, 2 * lenL + lenM_s);

                    // Case B: sub_s = L, sub_t = M + reverse(L)
                    int t_idx = m - j - 1;
                    int lenM_t = (t_idx >= 0) ? palLenTEnds[t_idx] : 0;
                    maxLen = Math.max(maxLen, 2 * lenL + lenM_t);
                }
            }
        }
        return maxLen;
    }
    // ... (helper methods for palindrome computation)
}
```
### Algorithm
*   **Base Cases**: Find the length of the longest palindromic substring within `s` and `t` separately. Initialize `maxLen` with the maximum of these two lengths.
*   **Palindrome Precomputation**: For both `s` and `t`, precompute information about palindromic substrings. Specifically, for each index `i`, find the length of the longest palindrome that starts at `i` and the length of the longest palindrome that ends at `i`. This can be done in O(N²) and O(M²) respectively.
*   **Reverse `t`**: Create a reversed version of `t`, let's call it `t_rev`.
*   **Find Common Substrings**: Use dynamic programming to find all common substrings between `s` and `t_rev`. Let `dp[i][j]` be the length of the common suffix of `s.substring(0, i)` and `t_rev.substring(0, j)`.
*   **Combine Parts**: Iterate through the `dp` table. If `dp[i][j] > 0`, it means we've found a common substring `L` of length `dp[i][j]` between `s` and `t_rev`. This `L` is a substring of `s`, and `reverse(L)` is a substring of `t`.
    *   **Case 1 (`sub_s = L+M, sub_t = reverse(L)`):** The palindrome is formed by `L` from `s`, followed by a palindromic part `M` also from `s`, and `reverse(L)` from `t`. The length is `2*len(L) + len(M)`. We use the precomputed data to find the length of the longest palindrome `M` starting immediately after `L` in `s`.
    *   **Case 2 (`sub_s = L, sub_t = M+reverse(L)`):** The palindrome is formed by `L` from `s`, `reverse(L)` from `t`, and a palindromic part `M` from `t` preceding `reverse(L)`. The length is `2*len(L) + len(M)`. We use precomputed data for `t`.
*   Update `maxLen` with the maximum length found from these cases and return it.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
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;
  }
};

```

### Python

```python
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

```