Problem statement

https://leetcode.com/problems/split-two-strings-to-make-palindrome/

Solution

The idea is if we can construct palindrome from two parts, we need to have the following pattern: imagine we have abcxyzyz*** and ********cba, then we have a prefix of the first string is equal to the revesed suffix of the second string. What we have in the middle must be palindrome: it must be palindrome for the first or for the second string. We can have 4 options in total:

  1. prefix of a, suffix of b, middle palindrome of a.
  2. prefix of a, suffix of b, middle palindrome of b.
  3. prefix of b, suffix of a, middle palindrome of a.
  4. prefix of b, suffix of a, middle palindrome of b.

Also we need to take care of options when strings are palindromes: then we can have empty strings as partitions.

Complexity

It is O(n) both for time and space.

Code

from os.path import commonprefix

class Solution:
    def checkPalindromeFormation(self, a, b):
        n = len(a)
        t1 = len(commonprefix([a, b[::-1]]))
        t2 = len(commonprefix([b, a[::-1]]))
        t3 = max(t1, t2)
        if t3*2 >= n: return True
        if a == a[::-1] or b == b[::-1]: return True
        if t3 > 0 and a[t3:-t3] == a[t3:-t3][::-1]: return True
        if t3 > 0 and b[t3:-t3] == b[t3:-t3][::-1]: return True
        return False