: Create dpt[i] = longest palindromic substring ending at index i

Initialize answer with single-string palindromes: Track the maximum palindrome length from s or t alone

Dynamic Programming for cross-string palindromes:

Start from the middle of both strings and work outward
Use DP to find palindromic combinations where characters from s match characters from t
For each matching pair, extend the palindrome and combine with precomputed palindromic substrings

Optimize with memoization: Cache results to avoid redundant computations and achieve better time complexity

Code

[{"language":"C++","code":"class Solution {\nprivate:\n    int ans;\n    vector<vector<int>> memo;\n    \n    vector<int> lpsStart(const string& s) {\n        int n = s.length();\n        vector<int> res(n, 1);\n        \n        for (int i = 0; i < n; i++) {\n            // Odd length palindromes\n            int len = expand(s, i, i);\n            if (i - len >= 0) {\n                res[i - len] = max(res[i - len], len * 2 + 1);\n            }\n            \n            // Even length palindromes\n            len = expand(s, i, i + 1);\n            if (len >= 0 && i - len >= 0) {\n                res[i - len] = max(res[i - len], len * 2 + 2);\n            }\n        }\n        return res;\n    }\n    \n    vector<int> lpsEnd(const string& s) {\n        int n = s.length();\n        vector<int> res(n, 1);\n        \n        for (int i = 0; i < n; i++) {\n            // Odd length palindromes\n            int len = expand(s, i, i);\n            if (i + len < n) {\n                res[i + len] = max(res[i + len], len * 2 + 1);\n            }\n            \n            // Even length palindromes\n            len = expand(s, i - 1, i);\n            if (len >= 0 && i + len < n) {\n                res[i + len] = max(res[i + len], len * 2 + 2);\n            }\n        }\n        return res;\n    }\n    \n    int expand(const string& s, int l, int r) {\n        int res = 0;\n        while (l >= 0 && r < s.length() && s[l] == s[r]) {\n            res++;\n            l--;\n            r++;\n        }\n        return res - 1;\n    }\n    \n    int find(const vector<int>& dps, const vector<int>& dpt, \n             const stri

Related Tags