# Longest Palindrome After Substring Concatenation I
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/longest-palindrome-after-substring-concatenation-i)
Canonical: https://scaleengineer.com/dsa/problems/longest-palindrome-after-substring-concatenation-i
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers), [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Enumeration](https://scaleengineer.com/dsa/patterns/enumeration)
**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 <= 30`
* `s` and `t` consist of lowercase English letters.

# Approaches
## Brute-Force Enumeration of Substrings
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.
**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.
**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.
### Explanation
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`.

```java
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;
    }
}
```
### Algorithm
*   Initialize a variable `maxLength` to 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 of `t` (`sub_t`), also including the empty string.
*   Concatenate the two substrings: `combined = sub_s + sub_t`.
*   If the `combined` string is not empty, check if it is a palindrome.
*   A helper function `isPalindrome(str)` can be used, which checks if `str` reads the same forwards and backwards.
*   If `combined` is a palindrome, update `maxLength = max(maxLength, combined.length())`.
*   After checking all pairs of substrings, return `maxLength`.

## Dynamic Programming on Common Substrings
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.
**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.
**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.
### Explanation
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:
1.  `s1` and `s2` are identical (forms an even-length palindrome).
2.  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.

```java
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;
    }
}
```
### Algorithm
*   First, handle the base cases where the palindrome lies entirely within `s` or `t`. Find the longest palindromic substring in each and initialize `maxLength`.
*   The core idea for combined palindromes `sub_s + sub_t` is that `sub_s` must align with `reverse(sub_t)`. Let `rev_t = reverse(t)`.
*   We look for a common substring `C` between `s` and `rev_t`. The resulting palindrome will have the structure `C + P + reverse(C)`, where `P` is another palindrome.
*   Precompute all palindromic substrings for `s` and `rev_t` using a 2D DP table (e.g., `isPal[i][j]`). This takes `O(N² + M²)`. 
*   From the `isPal` tables, compute `longestPalFrom[i]`, the length of the longest palindrome starting at index `i` for both `s` and `rev_t`.
*   Use another DP table to find lengths of all common substrings between `s` and `rev_t`. `dp[i][j]` will store the length of the common substring ending at `s[i-1]` and `rev_t[j-1]`.
*   Iterate through the common substring DP table. For each common substring `C` of length `k = dp[i][j]`:
    *   Consider the case where `sub_s = C + P_s` and `reverse(sub_t) = C`. The total length is `2*k + longestPalFrom[i]`. Update `maxLength`.
    *   Consider the case where `sub_s = C` and `reverse(sub_t) = C + P_t`. The total length is `2*k + longestPalFrom[j]` (for `rev_t`). Update `maxLength`.
*   The even-length case (where the middle palindrome `P` is empty) is implicitly handled as `longestPalFrom` can be 0.
*   Return the final `maxLength`.

# 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

```