2020-10-13
1616. Split Two Strings to Make Palindrome
Question:
You are given two strings a
and b
of the same length. Choose an index and split both strings at the same index, splitting a
into two strings: aprefix
and asuffix
where a = aprefix + asuffix
, and splitting b
into two strings: bprefix
and bsuffix
where b = bprefix + bsuffix
. Check if aprefix + bsuffix
or bprefix + asuffix
forms a palindrome.
When you split a string s
into sprefix
and ssuffix
, either ssuffix
or sprefix
is allowed to be empty. For example, if s = "abc"
, then "" + "abc"
, "a" + "bc"
, "ab" + "c"
, and "abc" + ""
are valid splits.
Return true
if it is possible to form a palindrome string, otherwise return false
.
Notice that x + y
denotes the concatenation of strings x
and y
.
Example 1:
Input: a = "x", b = "y"
Output: true
Explaination: If either a or b are palindromes the answer is true since you can split in the following way:
aprefix = "", asuffix = "x"
bprefix = "", bsuffix = "y"
Then, aprefix + bsuffix = "" + "y" = "y", which is a palindrome.
Example 2:
Input: a = "abdef", b = "fecab"
Output: true
Example 3:
Input: a = "ulacfd", b = "jizalu"
Output: true
Explaination: Split them at index 3:
aprefix = "ula", asuffix = "cfd"
bprefix = "jiz", bsuffix = "alu"
Then, aprefix + bsuffix = "ula" + "alu" = "ulaalu", which is a palindrome.
Example 4:
Input: a = "xbdef", b = "xecab"
Output: false
Constraints:
1 <= a.length, b.length <= 105
a.length == b.length
a
andb
consist of lowercase English letters
Solution:
Two pointer pointing to the start of first string and end of second string. Find the location until two characters are different and then check if each of the string is palindrome in the between range.
class Solution {
public boolean checkPalindromeFormation(String a, String b) {
return valid(a, b) || valid(b, a);
}
private boolean valid(String a, String b) {
int left = 0;
int right = a.length() - 1;
while (left < right) {
if (a.charAt(left) != b.charAt(right)) {
return isPalindrome(a, left, right) || isPalindrome(b, left, right);
}
left++;
right--;
}
return true;
}
private boolean isPalindrome(String a, int start, int end) {
while(start < end) {
if (a.charAt(start) != a.charAt(end)) {
return false;
}
start++;
end--;
}
return true;
}
}