3503. Longest Palindrome After Substring Concatenation I LeetCode Solution
In this guide, you will get 3503. Longest Palindrome After Substring Concatenation I LeetCode Solution with the best time and space complexity. The solution to Longest Palindrome After Substring Concatenation I problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Table of Contents
- Problem Statement
- Complexity Analysis
- Longest Palindrome After Substring Concatenation I solution in C++
- Longest Palindrome After Substring Concatenation I solution in Java
- Longest Palindrome After Substring Concatenation I solution in Python
- Additional Resources
Problem Statement of Longest Palindrome After Substring Concatenation I
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.
Complexity Analysis
- Time Complexity:
- Space Complexity:
3503. Longest Palindrome After Substring Concatenation I LeetCode Solution in C++
class Solution {
public:
int longestPalindrome(string s, string t) {
const int m = s.length();
const int n = t.length();
vector<int> suffix = getPalindromeLengths(s, true);
vector<int> prefix = getPalindromeLengths(t, false);
int ans = max(ranges::max(suffix), ranges::max(prefix));
// dp[i][j] := the longest length of palindrome starting in s[i] and ending
// in t[j]
vector<vector<int>> dp(m, vector<int>(n));
for (int i = 0; i < m; ++i)
for (int j = n - 1; j >= 0; --j)
if (s[i] == t[j]) {
dp[i][j] = 2 + (i > 0 && j < n - 1 ? dp[i - 1][j + 1] : 0);
const int extend =
max(i + 1 < m ? suffix[i + 1] : 0, j > 0 ? prefix[j - 1] : 0);
ans = max(ans, dp[i][j] + extend);
}
return ans;
}
private:
vector<int> getPalindromeLengths(const string& s, bool isSuffix) {
const int n = s.length();
// dp[i][j] := True if s[i..j] is a palindrome
vector<vector<bool>> dp(n, vector<bool>(n));
// lengths[i] := length of longest palindrome in s[i..n - 1]
vector<int> lengths(n);
for (int i = n - 1; i >= 0; --i)
for (int j = i; j < n; ++j)
if (s[i] == s[j] && (j - i < 2 || dp[i + 1][j - 1])) {
dp[i][j] = true;
const int index = isSuffix ? i : j;
lengths[index] = max(lengths[index], j - i + 1);
}
return lengths;
}
};
/* code provided by PROGIEZ */3503. Longest Palindrome After Substring Concatenation I LeetCode Solution in Java
class Solution {
public int longestPalindrome(String s, String t) {
final int m = s.length();
final int n = t.length();
int[] suffix = getPalindromeLengths(s, true);
int[] prefix = getPalindromeLengths(t, false);
int ans = Math.max(Arrays.stream(suffix).max().getAsInt(), //
Arrays.stream(prefix).max().getAsInt());
// dp[i][j] := the longest length of palindrome starting in s[i] and ending
// in t[j]
int[][] dp = new int[m][n];
for (int i = 0; i < m; ++i)
for (int j = n - 1; j >= 0; --j)
if (s.charAt(i) == t.charAt(j)) {
dp[i][j] = 2 + (i > 0 && j < n - 1 ? dp[i - 1][j + 1] : 0);
final int extend = Math.max(i + 1 < m ? suffix[i + 1] : 0, j > 0 ? prefix[j - 1] : 0);
ans = Math.max(ans, dp[i][j] + extend);
}
return ans;
}
private int[] getPalindromeLengths(String s, boolean isSuffix) {
final int n = s.length();
// dp[i][j] := True if s[i..j] is a palindrome
boolean[][] dp = new boolean[n][n];
// lengths[i] := length of longest palindrome in s[i..n - 1]
int[] lengths = new int[n];
for (int i = n - 1; i >= 0; --i)
for (int j = i; j < n; ++j)
if (s.charAt(i) == s.charAt(j) && (j - i < 2 || dp[i + 1][j - 1])) {
dp[i][j] = true;
final int index = isSuffix ? i : j;
lengths[index] = Math.max(lengths[index], j - i + 1);
}
return lengths;
}
}
// code provided by PROGIEZ3503. Longest Palindrome After Substring Concatenation I LeetCode Solution in Python
class Solution:
def longestPalindrome(self, s: str, t: str) -> int:
m = len(s)
n = len(t)
suffix = self._getPalindromeLengths(s, True)
prefix = self._getPalindromeLengths(t, False)
ans = max(max(suffix), max(prefix))
# dp[i][j] := the longest length of palindrome starting in s[i] and ending
# in t[j]
dp = [[0] * n for _ in range(m)]
for i in range(m):
for j in range(n - 1, -1, -1):
if s[i] == t[j]:
dp[i][j] = 2 + (dp[i - 1][j + 1] if i > 0 and j < n - 1 else 0)
extend = max(suffix[i + 1] if i + 1 < m else 0,
prefix[j - 1] if j > 0 else 0)
ans = max(ans, dp[i][j] + extend)
return ans
def _getPalindromeLengths(self, s: str, isSuffix: bool) -> list[int]:
n = len(s)
# dp[i][j] := True if s[i..j] is a palindrome
dp = [[False] * n for _ in range(n)]
# lengths[i] := length of longest palindrome in s[i..n - 1]
lengths = [0] * n
for i in range(n - 1, -1, -1):
for j in range(i, n):
if s[i] == s[j] and (j - i < 2 or dp[i + 1][j - 1]):
dp[i][j] = True
index = i if isSuffix else j
lengths[index] = max(lengths[index], j - i + 1)
return lengths
# code by PROGIEZAdditional Resources
- Explore all LeetCode problem solutions at Progiez here
- Explore all problems on LeetCode website here
Happy Coding! Keep following PROGIEZ for more updates and solutions.