LeetCode-in-Java
3503. Longest Palindrome After Substring Concatenation I
Medium
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 <= 30sandtconsist of lowercase English letters.
Solution
public class Solution {
public int longestPalindrome(String s, String t) {
int maxLen = 0;
maxLen = Math.max(maxLen, longestPalindromicSubstring(s));
maxLen = Math.max(maxLen, longestPalindromicSubstring(t));
int sLen = s.length();
int tLen = t.length();
for (int i = 0; i < sLen; i++) {
for (int j = i; j < sLen; j++) {
int m = j - i + 1;
for (int k = 0; k < tLen; k++) {
for (int l = k; l < tLen; l++) {
int n = l - k + 1;
int totalLength = m + n;
if (totalLength <= maxLen) {
continue;
}
boolean isPalindrome = true;
for (int p = 0; p < totalLength / 2; p++) {
int q = totalLength - 1 - p;
char c1;
char c2;
if (p < m) {
c1 = s.charAt(i + p);
} else {
c1 = t.charAt(k + (p - m));
}
if (q < m) {
c2 = s.charAt(i + q);
} else {
c2 = t.charAt(k + (q - m));
}
if (c1 != c2) {
isPalindrome = false;
break;
}
}
if (isPalindrome) {
maxLen = totalLength;
}
}
}
}
}
return maxLen;
}
private int longestPalindromicSubstring(String str) {
int max = 0;
int len = str.length();
for (int i = 0; i < len; i++) {
for (int j = i; j < len; j++) {
boolean isPalin = true;
int left = i;
int right = j;
while (left < right) {
if (str.charAt(left) != str.charAt(right)) {
isPalin = false;
break;
}
left++;
right--;
}
if (isPalin) {
max = Math.max(max, j - i + 1);
}
}
}
return max;
}
}