3504. Longest Palindrome After Substring Concatenation II

HardTwo PointersStringDynamic Programming

Problem Description

You are given two strings, s and t. You can create a new string by selecting a substring from s (which can be empty) and a substring from t (which can also be empty), then concatenating these substrings in order. The goal is to find the length of the longest palindrome that can be formed this way.

Intuition

The problem involves finding palindromes that can be constructed by concatenating substrings from the provided strings s and t. A palindrome is a string that reads the same backward as forward. The solution requires considering palindromes formed entirely from s, entirely from t, or a combination of both.

To approach this problem, we need to utilize dynamic programming and palindrome center enumeration. First, reverse the string t, as reversing helps us align potential palindromic sections from s with t. We preprocess two arrays, g1 and g2, to track the length of the longest palindromic substring starting at each position in s and reversed t, respectively.

The main idea is to dynamically calculate a matrix f where f[i][j] represents the length of the palindromic substring ending at the i-th character of s and the j-th character of t. If characters at these positions are identical, f[i][j] is incremented based on the previous state f[i-1][j-1].

The solution proceeds by maximally updating ans to ensure it reflects the longest possible palindrome length. Each potential palindrome length considers contributions from the palindromic substrings within s or t.

Learn more about Two Pointers and Dynamic Programming patterns.

Solution Approach

The solution leverages a combination of dynamic programming and palindrome center expansion. Here's a step-by-step walkthrough of the implementation:

Reverse and Preprocess: Start by reversing the string t. This facilitates comparing and aligning parts of s with parts of t to form palindromes. Preprocess arrays g1 and g2 to store the lengths of the longest palindromic substrings starting at each index in s and reversed t, respectively.

Palindrome Expansion Function: Implement a helper function expand(s: str, g: List[int], l: int, r: int) to update the g array. This function expands around a center (or centers, in case of even-length palindromes) to find the maximum palindrome length:

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

Calculate Longest Palindromes: Use calc(s: str) -> List[int] to apply expand across the entire string for both s and reversed t, generating g1 and g2.
Dynamic Programming Table: Initialize a matrix f of size (m+1) x (n+1) where m is the length of s and n is the length of t. This table will store the maximum length of palindromic substrings that can be constructed ending at certain indices of s and t.
Update Maximum Length: Traverse each character combination in s and reversed t:
- If the characters match (s[i-1] == t[j-1]), extend the palindrome by setting f[i][j] = f[i-1][j-1] + 1.
- Use f[i][j] to update the maximum palindrome length (ans), considering the precomputed palindromic lengths from g1 and g2.
Result Extraction: The maximum value found in the dynamic programming process and precomputed arrays gives the length of the longest possible palindrome.

By combining these steps, the solution efficiently finds the desired longest palindrome using dynamic programming and substring expansion techniques.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's consider an example where s = "abac" and t = "cab". Our goal is to find the length of the longest palindrome that can be formed by concatenating substrings from s and t.

Reverse and Preprocess: First, reverse string t, resulting in reversed_t = "bac". We need to preprocess arrays g1 for s and g2 for reversed_t using the expand function to determine the longest palindromic substring that starts at each index.
- For s = "abac", the longest palindromic substrings starting at each index are: g1 = [1, 3, 1, 1] (e.g., "aba" is the longest palindrome starting at index 1).
- For reversed_t = "bac", calculate: g2 = [1, 1, 1].
Palindrome Expansion Function: The expand function will assess each character in both strings to determine the span of palindromic substrings. For instance, in s = "abac", the center expansion reveals that "aba" is a palindrome starting at index 1.
Calculate Longest Palindromes: Use these arrays to evaluate potential palindromes within each string individually.

Dynamic Programming Table: Define a matrix f of size (5 x 4) (since s has 4 characters and t has 3, plus one extra for indexing from 1). This matrix will store the palindromic lengths:

f = [
    [0, 0, 0, 0],
    [0, 0, 0, 0],
    [0, 0, 0, 0],
    [0, 0, 0, 0],
    [0, 0, 0, 0]
]

Update Maximum Length: Traverse each combination of characters from s and reversed_t:
- For i = 1 and j = 2, where s[0] = 'a' and t[1] = 'a', set f[1][2] = f[0][1] + 1 = 1.
- For i = 3 and j = 1, where s[2] = 'a' and t[0] = 'c', no update occurs since characters do not match.
- Continue this for all combinations.
Result Extraction: Throughout this process, track the maximum value in f and utilize g1 and g2 to help account for palindromes formed entirely within s or t. By the end, the maximum found across all checks gives the length of the longest possible palindrome, which in this case is 3, corresponding to either "aba" from s or a combination like "aca" from s and reversed t.

By applying these steps, the longest palindrome in this example is "aba" with a length of 3.

Solution Implementation

1from typing import List
2
3class Solution:
4    def longestPalindrome(self, s: str, t: str) -> int:
5        # Helper function to expand around the center and update the maximum palindrome lengths
6        def expand_around_center(s: str, pal_lengths: List[int], left: int, right: int):
7            while left >= 0 and right < len(s) and s[left] == s[right]:
8                pal_lengths[left] = max(pal_lengths[left], right - left + 1)
9                left -= 1
10                right += 1
11
12        # Function to calculate the longest palindromic substring lengths for each position
13        def calc_palindrome_lengths(s: str) -> List[int]:
14            n = len(s)
15            pal_lengths = [0] * n
16            for i in range(n):
17                expand_around_center(s, pal_lengths, i, i)     # Odd-length palindromes
18                expand_around_center(s, pal_lengths, i, i + 1) # Even-length palindromes
19            return pal_lengths
20
21        m, n = len(s), len(t)
22        reversed_t = t[::-1]  # Reverse the string t
23        s_palindrome_lengths = calc_palindrome_lengths(s)
24        t_palindrome_lengths = calc_palindrome_lengths(reversed_t)
25
26        # Initial maximum length is the largest single palindromic substring found in s or t
27        max_length = max(*s_palindrome_lengths, *t_palindrome_lengths)
28
29        # Initialize the dynamic programming table
30        dp = [[0] * (n + 1) for _ in range(m + 1)]
31
32        # Calculate the longest palindromic subsequence
33        for i in range(1, m + 1):
34            for j in range(1, n + 1):
35                if s[i - 1] == reversed_t[j - 1]:
36                    dp[i][j] = dp[i - 1][j - 1] + 1
37                    # Check and update maximum length considering both sequences
38                    max_length = max(max_length, dp[i][j] * 2 + (0 if i >= m else s_palindrome_lengths[i]))
39                    max_length = max(max_length, dp[i][j] * 2 + (0 if j >= n else t_palindrome_lengths[j]))
40
41        return max_length
42

1import java.util.Arrays;
2
3class Solution {
4    public int longestPalindrome(String S, String T) {
5        // Convert strings to character arrays
6        char[] s = S.toCharArray();
7        // Reverse string T and convert to character array
8        char[] t = new StringBuilder(T).reverse().toString().toCharArray();
9        int m = s.length, n = t.length;
10        // Calculate expanded lengths for both strings
11        int[] maxExpandsInS = calc(s);
12        int[] maxExpandsInT = calc(t);
13      
14        // Find the maximum length of palindromes in either of the strings using prefix expansions
15        int maxLength = Math.max(Arrays.stream(maxExpandsInS).max().getAsInt(), Arrays.stream(maxExpandsInT).max().getAsInt());
16      
17        // Create a dynamic programming table to find the longest common subsequence
18        int[][] lcsLengths = new int[m + 1][n + 1];
19      
20        // Fill the dynamic programming table
21        for (int i = 1; i <= m; ++i) {
22            for (int j = 1; j <= n; ++j) {
23                if (s[i - 1] == t[j - 1]) { // If characters match
24                    lcsLengths[i][j] = lcsLengths[i - 1][j - 1] + 1; // Extend the common subsequence
25                    // Calculate potential palindrome lengths by combining sequence with expansions
26                    maxLength = Math.max(maxLength, lcsLengths[i][j] * 2 + (i < m ? maxExpandsInS[i] : 0));
27                    maxLength = Math.max(maxLength, lcsLengths[i][j] * 2 + (j < n ? maxExpandsInT[j] : 0));
28                }
29            }
30        }
31        // Return the maximum length of a potential palindrome
32        return maxLength;
33    }
34
35    private void expand(char[] s, int[] expandArray, int left, int right) {
36        // Expand around the center as long as characters match and stay within array bounds
37        while (left >= 0 && right < s.length && s[left] == s[right]) {
38            // Record the maximum length of expanded palindromes
39            expandArray[left] = Math.max(expandArray[left], right - left + 1);
40            --left; // Expand to the left
41            ++right; // Expand to the right
42        }
43    }
44
45    private int[] calc(char[] s) {
46        int length = s.length;
47        int[] expandLengths = new int[length];
48        for (int i = 0; i < length; ++i) {
49            expand(s, expandLengths, i, i); // Expand around a single character
50            expand(s, expandLengths, i, i + 1); // Expand around a pair of characters
51        }
52        return expandLengths;
53    }
54}
55

1#include <string>
2#include <vector>
3#include <algorithm>
4#include <ranges> // This requires C++20
5using namespace std;
6
7class Solution {
8public:
9    int longestPalindrome(string s, string t) {
10        // Get the sizes of strings s and t
11        int m = s.size(), n = t.size();
12
13        // Reverse the string t
14        ranges::reverse(t);
15
16        // Calculate the maximum expand palindromic substrings lengths for s and reversed t
17        vector<int> g1 = calc(s), g2 = calc(t);
18
19        // Find initial answer as the maximum between the largest palindrome expansions in g1 and g2
20        int ans = max(ranges::max(g1), ranges::max(g2));
21
22        // Initialize a DP table with m+1 rows and n+1 columns, filled with zeros
23        vector<vector<int>> f(m + 1, vector<int>(n + 1, 0));
24
25        // Loop through each character in s and t
26        for (int i = 1; i <= m; ++i) {
27            for (int j = 1; j <= n; ++j) {
28                // Check if characters from s and reversed t match
29                if (s[i - 1] == t[j - 1]) {
30                    // Update dp table with diagonal plus one, indicating longest common subsequence so far
31                    f[i][j] = f[i - 1][j - 1] + 1;
32
33                    // Update the answer by considering current palindrome length multiplied by 2,
34                    // and adding residual palindromic length from g1 or g2 if possible
35                    ans = max(ans, f[i][j] * 2 + (i < m ? g1[i] : 0));
36                    ans = max(ans, f[i][j] * 2 + (j < n ? g2[j] : 0));
37                }
38            }
39        }
40
41        // Return the longest palindromic length found
42        return ans;
43    }
44
45private:
46    // Helper function to expand and find palindromes around a center (l, r)
47    void expand(const string& s, vector<int>& g, int l, int r) {
48        // Expand as long as the characters match and indices are within bounds
49        while (l >= 0 && r < s.size() && s[l] == s[r]) {
50            // Update maximum palindrome length centered at l
51            g[l] = max(g[l], r - l + 1);
52
53            // Expand further by moving outwards
54            --l;
55            ++r;
56        }
57    }
58
59    // Function to calculate maximum palindrome expansion for each character in the string
60    vector<int> calc(const string& s) {
61        int n = s.size();
62        vector<int> g(n, 0);
63
64        // Calculate for each character considering both odd and even length palindromes
65        for (int i = 0; i < n; ++i) {
66            expand(s, g, i, i);     // Odd length palindrome
67            expand(s, g, i, i + 1); // Even length palindrome
68        }
69
70        // Return the calculated expansions
71        return g;
72    }
73};
74

1function longestPalindrome(s: string, t: string): number {
2    /**
3     * Helper function expand checks how far the palindrome can extend from the center index `l` and `r`.
4     *
5     * @param s - The input string.
6     * @param palindromeLengths - Array storing maximum palindrome lengths centered at each index.
7     * @param l - The left center index.
8     * @param r - The right center index.
9     */
10    function expand(s: string, palindromeLengths: number[], l: number, r: number): void {
11        // Extend the palindrome while the characters at the expanding edges match
12        while (l >= 0 && r < s.length && s[l] === s[r]) {
13            palindromeLengths[l] = Math.max(palindromeLengths[l], r - l + 1);
14            l--;
15            r++;
16        }
17    }
18
19    /**
20     * Computes the maximum lengths of palindromes centered at each index in the string.
21     *
22     * @param s - The input string.
23     * @returns An array with the maximum palindrome lengths at each center position.
24     */
25    function calc(s: string): number[] {
26        const n = s.length;
27        const palindromeLengths: number[] = Array(n).fill(0);
28        for (let i = 0; i < n; i++) {
29            expand(s, palindromeLengths, i, i);     // Odd-length palindromes
30            expand(s, palindromeLengths, i, i + 1); // Even-length palindromes
31        }
32        return palindromeLengths;
33    }
34
35    // Reverse the second string
36    t = t.split('').reverse().join('');
37  
38    // Calculate palindrome lengths in `s` and `t`
39    const palindromeLengthsInS = calc(s);
40    const palindromeLengthsInT = calc(t);
41  
42    // Max palindrome length found in individual strings
43    let maxPalindromeLength = Math.max(...palindromeLengthsInS, ...palindromeLengthsInT);
44
45    const m = s.length;
46    const n = t.length;
47
48    // Dynamic programming table to store longest common subsequence length
49    const dp: number[][] = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));
50
51    // Build the table and find longest combined palindrome using the LCS
52    for (let i = 1; i <= m; i++) {
53        for (let j = 1; j <= n; j++) {
54            if (s[i - 1] === t[j - 1]) {
55                dp[i][j] = dp[i - 1][j - 1] + 1; // Extend the LCS if characters match
56                maxPalindromeLength = Math.max(
57                    maxPalindromeLength,
58                    dp[i][j] * 2 + (i >= m ? 0 : palindromeLengthsInS[i]), // Extend palindromes involving `s`
59                    dp[i][j] * 2 + (j >= n ? 0 : palindromeLengthsInT[j])  // Extend palindromes involving `t`
60                );
61            }
62        }
63    }
64
65    return maxPalindromeLength; // Return the length of the longest palindrome found
66}
67

Time and Space Complexity

The time complexity of the solution can be analyzed as follows:

calc(s) is called twice: once for s and once for the reversed t. This involves iterating over each character in the string and expanding around each character to check for palindromes. The expand function may take up to O(m) and O(n) time respectively for s and t. Therefore, calc for both strings takes O(m^2 + n^2) time in the worst case.
The nested loop over s and t runs in O(m * n) time since it iterates over each character pair from s and t.

Therefore, the total time complexity is O(m^2 + n^2 + m * n). In the reference answer, the time complexity is given as O(m \times (m + n)), which aligns with the expanded form O(m^2 + m * n) since m is assumed to dominate when m and n are close in magnitude.

The space complexity is analyzed as follows:

The calc function uses a list g of size n for each string, contributing O(m + n) space.
The f matrix is of size (m + 1) x (n + 1), which contributes O(m * n) space.

Thus, the total space complexity is O(m * n), consistent with the reference answer.

Learn more about how to find time and space complexity quickly.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan: