Facebook Pixel

3503. Longest Palindrome After Substring Concatenation I

MediumTwo PointersStringDynamic ProgrammingEnumeration
Leetcode Link

Problem Description

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.

Intuition

To tackle this problem, one needs to understand how palindromes work within the context of combining substrings from two different strings.

  1. Concept of Palindromes: A palindrome is a sequence that reads the same forward and backward. When considering substrings from s and t, they can be combined to potentially form a palindrome, where the portion from s is followed by that from a reversed t.

  2. Reversing String t: By reversing t, the problem reduces to finding a palindromic subsequence through the combination of s and this reversed version of t. This helps in determining the longest common palindrome sequence when s[i] equals t[j].

  3. Dynamic Programming Approach:

    • Use dynamic programming (DP) to keep track of the longest palindromic subsequences ending at different indices.
    • Calculate f[i][j], which represents the length of a palindromic sequence ending at the i-th character of s and j-th character of t.

  4. Preprocessing for Longest Palindromic Substrings:

    • Compute two arrays, g1 and g2, for the longest palindromic substrings starting at each index of s and t respectively.
    • Evaluate the current answer (ans) by possibly extending these known palindromes using the DP table.

By understanding these key steps and applying the combination of dynamic programming and preprocessing, the problem of finding the longest possible palindrome becomes manageable. The solution effectively handles the possibility of using any part of s or t or their combination, maintaining an efficient approach towards obtaining the maximum palindrome length.

Learn more about Two Pointers and Dynamic Programming patterns.

Solution Approach

Solution 1: Enumerate Palindrome Centers + Dynamic Programming

According to the problem description, the concatenated palindrome string can be composed entirely of string s, entirely of string t, or a combination of both strings s and t. Additionally, there may be extra palindromic substrings in either string s or t.

Firstly, we reverse string t and preprocess arrays g1 and g2. Here, g1[i] represents the length of the longest palindromic substring starting at index i in string s, and g2[i] represents the length of the longest palindromic substring starting at index i in string t.

The initial answer ans is set to the maximum value found in g1 and g2, capturing the longest possible palindromic substring in either s or t alone.

We define a dynamic programming table f[i][j] which captures the length of the palindromic substring ending at the i-th character of s and the j-th character of t.

For f[i][j], if s[i - 1] equals t[j - 1], then the formula is: [ f[i][j] = f[i - 1][j - 1] + 1 ] This indicates that the palindromic sequence can be extended by one character from both strings.

We update the answer ans as follows: [ ans = \max(ans, f[i][j] \times 2 + (0 \text{ if } i \geq m \text{ else } g1[i])) ] [ ans = \max(ans, f[i][j] \times 2 + (0 \text{ if } j \geq n \text{ else } g2[j])) ]

These calculations allow the length of the palindrome to account for any additional palindromic sequences extending from the substrings of s or reversed t.

Finally, the solution returns the computed maximum palindrome length ans.

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 the example where s = "abc" and t = "dcb".

Step 1: Palindrome Concept and Reverse String t

  • We need to find palindromic sequences by potentially concatenating substring from s and t.
  • Reverse string t to get reversed_t = "bcd".

Step 2: Preprocess Longest Palindromic Substrings

  • Initialize g1 and g2 to store the longest palindromic substrings starting at each index for s and reversed_t.
  • For s = "abc", the palindromic substrings starting at each index are single characters ("a", "b", "c"), thus g1 = [1, 1, 1].
  • For reversed_t = "bcd", similarly the palindromic substrings are single characters ("b", "c", "d"), thus g2 = [1, 1, 1].

Step 3: Initialize Answer

  • Set ans to the maximum value found in g1 and g2, which is 1.

Step 4: Dynamic Programming Table f[i][j]

  • Create a DP table f[i][j] for 0 ≤ i ≤ len(s) and 0 ≤ j ≤ len(reversed_t).

Step 5: Fill the DP Table

  • Loop over each character in s and reversed_t. If s[i - 1] equals reversed_t[j - 1], set f[i][j] = f[i - 1][j - 1] + 1.

Let's fill the table:

  • s[0] = "a", reversed_t[0] = "b" (not equal), so f[1][1] = 0.
  • s[1] = "b", reversed_t[0] = "b" (equal), so f[2][1] = f[1][0] + 1 = 1.
  • For rest, we similarly find that f[3][2] = 1 due to s[2] = "c" and reversed_t[1] = "c" being equal.

Step 6: Update the Answer

  • Calculate potential palindromic lengths by considering extensions:

    • ans = max(ans, f[i][j] * 2 + (0 if i >= len(s) else g1[i]))
    • ans = max(ans, f[i][j] * 2 + (0 if j >= len(reversed_t) else g2[j]))

  • After evaluating sequences, the maximum ans value is 1 * 2 = 2.

The computed maximum palindrome length is 2.

Solution Implementation

1from typing import List
2
3class Solution:
4    def longestPalindrome(self, s: str, t: str) -> int:
5        # Helper function to expand around potential palindrome centers
6        def expand(partial: str, pal_lengths: List[int], left: int, right: int):
7            # Expand while the characters match and indices are within bounds
8            while left >= 0 and right < len(partial) and partial[left] == partial[right]:
9                pal_lengths[left] = max(pal_lengths[left], right - left + 1)
10                left -= 1
11                right += 1
12
13        # Function to calculate the maximum palindrome length from each character index
14        def calc(partial: str) -> List[int]:
15            n = len(partial)
16            pal_lengths = [0] * n
17            for i in range(n):
18                # Check for odd-length palindromes
19                expand(partial, pal_lengths, i, i)
20                # Check for even-length palindromes
21                expand(partial, pal_lengths, i, i + 1)
22            return pal_lengths
23
24        # Reverse the string t
25        reversed_t = t[::-1]
26        # Calculate max palindrome lengths for both strings
27        pal_in_s, pal_in_t = calc(s), calc(reversed_t)
28
29        # Initialize the maximum answer with the largest single string palindrome found
30        max_palindrome_length = max(*pal_in_s, *pal_in_t)
31
32        # Create a 2D list to store common substring lengths
33        common_substring_lengths = [[0] * (len(t) + 1) for _ in range(len(s) + 1)]
34
35        # Iterate over both strings to compute longest palindromic substring via dynamic programming
36        for i, char_s in enumerate(s, 1):
37            for j, char_t in enumerate(reversed_t, 1):
38                if char_s == char_t:
39                    # Update the common substring length
40                    common_substring_lengths[i][j] = common_substring_lengths[i - 1][j - 1] + 1
41                    # Calculate the palindrome lengths considering the common substring in s
42                    if i < len(s):
43                        current_pal_length = common_substring_lengths[i][j] * 2 + pal_in_s[i]
44                    else:
45                        current_pal_length = common_substring_lengths[i][j] * 2
46                    max_palindrome_length = max(max_palindrome_length, current_pal_length)
47
48                    # Calculate the palindrome lengths considering the common substring in t
49                    if j < len(t):
50                        current_pal_length = common_substring_lengths[i][j] * 2 + pal_in_t[j]
51                    else:
52                        current_pal_length = common_substring_lengths[i][j] * 2
53                    max_palindrome_length = max(max_palindrome_length, current_pal_length)
54
55        return max_palindrome_length
56
1class Solution {
2    public int longestPalindrome(String S, String T) {
3        // Convert strings to char arrays
4        char[] sArray = S.toCharArray();
5        char[] tArrayReversed = new StringBuilder(T).reverse().toString().toCharArray();
6      
7        int m = sArray.length, n = tArrayReversed.length;
8      
9        // Calculate max palindrome lengths from both ends
10        int[] palindromeLengthS = calc(sArray);
11        int[] palindromeLengthT = calc(tArrayReversed);
12      
13        // Find the maximum initial palindrome length
14        int maxPalindromeLength = Math.max(Arrays.stream(palindromeLengthS).max().getAsInt(), 
15                                           Arrays.stream(palindromeLengthT).max().getAsInt());
16      
17        // Initialize dynamic programming table
18        int[][] dp = new int[m + 1][n + 1];
19      
20        // Fill the DP table
21        for (int i = 1; i <= m; ++i) {
22            for (int j = 1; j <= n; ++j) {
23                // Check if characters match
24                if (sArray[i - 1] == tArrayReversed[j - 1]) {
25                    dp[i][j] = dp[i - 1][j - 1] + 1;
26                  
27                    // Update maxPalindromeLength considering potential palindrome expansion
28                    maxPalindromeLength = Math.max(maxPalindromeLength, dp[i][j] * 2 + (i < m ? palindromeLengthS[i] : 0));
29                    maxPalindromeLength = Math.max(maxPalindromeLength, dp[i][j] * 2 + (j < n ? palindromeLengthT[j] : 0));
30                }
31            }
32        }
33      
34        return maxPalindromeLength;
35    }
36
37    // Expands palindromes centered at indices l and r
38    private void expand(char[] s, int[] palindromeLengths, int left, int right) {
39        while (left >= 0 && right < s.length && s[left] == s[right]) {
40            palindromeLengths[left] = Math.max(palindromeLengths[left], right - left + 1);
41            --left;
42            ++right;
43        }
44    }
45
46    // Calculate max palindrome lengths for each center position
47    private int[] calc(char[] s) {
48        int n = s.length;
49        int[] palindromeLengths = new int[n];
50      
51        for (int i = 0; i < n; ++i) {
52            // Expand palindromes with single and double character centers
53            expand(s, palindromeLengths, i, i);
54            expand(s, palindromeLengths, i, i + 1);
55        }
56      
57        return palindromeLengths;
58    }
59}
60
1#include <string>
2#include <vector>
3#include <algorithm> // For std::max
4
5class Solution {
6public:
7    int longestPalindrome(std::string s, std::string t) {
8        int m = s.size(), n = t.size();
9
10        // Reverse 't' string for comparison
11        std::reverse(t.begin(), t.end());
12
13        // Get longest palindromic substring lengths for 's' and 't'
14        std::vector<int> g1 = calc(s), g2 = calc(t);
15
16        // Initialize 'ans' with the maximum of g1 and g2
17        int ans = std::max(*std::max_element(g1.begin(), g1.end()), *std::max_element(g2.begin(), g2.end()));
18
19        // DP table to store the length of common substrings between 's' and 't'
20        std::vector<std::vector<int>> f(m + 1, std::vector<int>(n + 1, 0));
21
22        for (int i = 1; i <= m; ++i) {
23            for (int j = 1; j <= n; ++j) {
24                // If characters match, extend the common substring
25                if (s[i - 1] == t[j - 1]) {
26                    f[i][j] = f[i - 1][j - 1] + 1;
27
28                    // Update the max length taking into account potential palindromes
29                    ans = std::max(ans, f[i][j] * 2 + (i < m ? g1[i] : 0));
30                    ans = std::max(ans, f[i][j] * 2 + (j < n ? g2[j] : 0));
31                }
32            }
33        }
34
35        return ans;
36    }
37
38private:
39    void expand(const std::string& s, std::vector<int>& g, int l, int r) {
40        // Expand around center to find the longest palindrome
41        while (l >= 0 && r < s.size() && s[l] == s[r]) {
42            g[l] = std::max(g[l], r - l + 1); // Update the max palindrome length
43            --l;
44            ++r;
45        }
46    }
47
48    std::vector<int> calc(const std::string& s) {
49        int n = s.size();
50        std::vector<int> g(n, 0); // Initialize palindrome lengths
51
52        for (int i = 0; i < n; ++i) {
53            // Find longest odd-length palindrome centered at 'i'
54            expand(s, g, i, i);
55            // Find longest even-length palindrome centered between 'i' and 'i+1'
56            expand(s, g, i, i + 1);
57        }
58
59        return g; // Return the palindrome lengths
60    }
61};
62
1/**
2 * This function finds the length of the longest palindrome that can be constructed
3 * from substrings of 's' and 't'.
4 * @param s - The first input string.
5 * @param t - The second input string.
6 * @returns The length of the longest palindrome possible.
7 */
8function longestPalindrome(s: string, t: string): number {
9
10    /**
11     * Expands around center and updates the palindrome lengths array 'g'
12     * for a given left 'l' and right 'r' center.
13     * @param s - The string being processed.
14     * @param g - The array maintaining palindrome lengths centered at each index.
15     * @param l - The left index from where to start expansion.
16     * @param r - The right index from where to start expansion.
17     */
18    function expand(s: string, g: number[], l: number, r: number): void {
19        while (l >= 0 && r < s.length && s[l] === s[r]) {
20            // Update to capture the length of the current palindrome
21            g[l] = Math.max(g[l], r - l + 1);
22          
23            // Move one step outwards
24            l--;
25            r++;
26        }
27    }
28
29    /**
30     * Calculates the maximum length of palindromes centered at each position in the string.
31     * @param s - The input string to calculate palindrome lengths.
32     * @returns An array containing the max palindrome length centered at each position.
33     */
34    function calc(s: string): number[] {
35        const n = s.length;
36        const g: number[] = Array(n).fill(0);
37      
38        // Check palindromes of both odd and even lengths centered at every index
39        for (let i = 0; i < n; i++) {
40            expand(s, g, i, i);     // Odd length palindromes
41            expand(s, g, i, i + 1); // Even length palindromes
42        }
43      
44        return g;
45    }
46
47    const m = s.length, n = t.length;
48    t = t.split('').reverse().join(''); // Reverse 't' to compare with 's'
49  
50    const g1 = calc(s); // Palindrome lengths for 's'
51    const g2 = calc(t); // Palindrome lengths for reversed 't'
52  
53    // Initial max palindrome length from individual characters
54    let ans = Math.max(...g1, ...g2);
55
56    // DP table to store the lengths of longest common substrings
57    const f: number[][] = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));
58
59    for (let i = 1; i <= m; i++) {
60        for (let j = 1; j <= n; j++) {
61            if (s[i - 1] === t[j - 1]) {
62                f[i][j] = f[i - 1][j - 1] + 1; // Length of LCS increases by 1
63              
64                // Calculates max palindrome length by considering substrings
65                ans = Math.max(ans, f[i][j] * 2 + (i >= m ? 0 : g1[i]));
66                ans = Math.max(ans, f[i][j] * 2 + (j >= n ? 0 : g2[j]));
67            }
68        }
69    }
70
71    return ans;
72}
73

Time and Space Complexity

The function calc(s) is called twice. During each call, it iterates over the string s of length m and performs the expand operation twice for each character, which is bounded by O(m) operations in the worst case. This results in O(m^2) complexity for each calc call. Thus, the combined complexity of both calc calls is O(m^2 + n^2).

The main loop through the f[i][j] matrix runs m * n iterations, each time performing constant time operations. Consequently, this contributes O(m * n) to the overall complexity.

Therefore, the total time complexity is O(m^2 + n^2 + m * n). Given m and n can vary independently, the time complexity can be simplified as O(m \times (m + n)).

The space complexity is primarily due to the matrix f of size (m+1) * (n+1), leading to O(m * n) space usage.

Hence, the space complexity of the code is O(m \times n).

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:

Which algorithm is best for finding the shortest distance between two points in an unweighted graph?

Recommended Readings

Tech Interview Pattern | Two Pointers Introduction

Tech Interview Pattern Two Pointers Introduction If you prefer videos here's a super quick introduction to Two Pointers div class responsive iframe iframe src https www youtube com embed xZ4AfXHQ1VQ title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture allowfullscreen iframe div Two pointers is a common interview

Dynamic Programming Introduction and Patterns

What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution

Coding Interview Patterns: The Smart, Data-Driven Way to Prepare for Tech Interviews

Coding Interview Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More