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` and `b` 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;
}
}
``````