Link

Medium Greedy

Google

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;
    }
}