Split Two Strings to Make Palindrome

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: a_prefix and a_suffix where a = a_prefix + a_suffix, and splitting b into two strings: b_prefix and b_suffix where b = b_prefix + b_suffix. Check if a_prefix + b_suffix or b_prefix + a_suffix forms a palindrome.

When you split a string s into s_prefix and s_suffix, either s_suffix or s_prefix 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.

For example: Input: a = "x", b = "y" Output: true

Input: a = "xbdef", b = "xecab" Output: false

Input: a = "ulacfd", b = "jizalu" Output: true. Split them at index 3: a_prefix = "ula", a_suffix = "cfd" b_prefix = "jiz", b_suffix = "alu" Then, a_prefix + b_suffix = "ula" + "alu" = "ulaalu", which is a palindrome.

Code Solution

def checkPalindromeFormation(a: str, b: str) -> bool:
    def isPalindrome(s: str) -> bool:
        return s == s[::-1]

    def check(a: str, b: str) -> bool:
        n = len(a)
        i, j = 0, n - 1
        while i < j and a[i] == b[j]:
            i += 1
            j -= 1
        if i >= j:
            return True
        sub_a = a[i:j+1]
        sub_b = b[i:j+1]
        return isPalindrome(sub_a) or isPalindrome(sub_b)

    return check(a, b) or check(b, a)

Explanation

The problem requires us to check if we can split two strings a and b of the same length at any index such that either a_prefix + b_suffix or b_prefix + a_suffix forms a palindrome. We can either take a prefix from string a and a suffix from string b, or a prefix from string b and a suffix from string a. The key idea is to iterate from the start and end of the strings simultaneously. If we find a mismatch, we consider the remaining substrings of both strings and check if either of them forms a palindrome.

1. isPalindrome(s) function:

   • This helper function checks if a given string s is a palindrome by comparing it to its reverse.

2. check(a, b) function:

   • This helper function takes two strings a and b and checks if a palindrome can be formed by combining a prefix of a and a suffix of b.
   • It uses two pointers, i and j, starting from the beginning of a and the end of b, respectively.
   • It advances the pointers as long as the characters at a[i] and b[j] match.
   • If the pointers cross or meet (i >= j), it means the combined string is already a palindrome, so it returns True.
   • If a mismatch is found, it extracts the remaining substrings a[i:j+1] and b[i:j+1] and checks if either of them is a palindrome.
   • If either substring is a palindrome, it returns True; otherwise, it returns False.

3. checkPalindromeFormation(a, b) function:

   • This is the main function that calls the check function twice: once with a and b and once with b and a.
   • It returns True if either of these calls returns True, indicating that a palindrome can be formed; otherwise, it returns False.

Example Walkthrough

Let's trace the execution with the input a = "ulacfd", b = "jizalu":

1. checkPalindromeFormation("ulacfd", "jizalu") is called.
2. check("ulacfd", "jizalu") is called.
   • i = 0, j = 5
   • a[0] = 'u', b[5] = 'u' (match)
   • i = 1, j = 4
   • a[1] = 'l', b[4] = 'l' (match)
   • i = 2, j = 3
   • a[2] = 'a', b[3] = 'a' (match)
   • i = 3, j = 2
   • Loop terminates because i > j.
   • The function returns True.
3. checkPalindromeFormation returns True.

Big(O) Runtime Analysis

The runtime complexity of the checkPalindromeFormation function is O(n), where n is the length of the input strings. This is because the check function iterates through the strings at most once, and the isPalindrome function also takes O(n) time in the worst case. Since check is called twice, the overall time complexity remains O(n).

Big(O) Space Usage Analysis

The space complexity of the checkPalindromeFormation function is O(n) in the worst case, where n is the length of the input strings. This is because in the check function, sub_a and sub_b can hold substrings of length n. The isPalindrome function, in its implementation, creates a reversed copy of a string of size n as well, leading to O(n) space.

Edge Cases

1. Empty strings: If either a or b are empty, the function will still work correctly because the loop condition i < j will immediately fail, and the subsequent palindrome check will be performed on empty substrings. An empty string is considered a palindrome.
2. Single-character strings: If a and b are single characters, the function will correctly identify whether the concatenation is a palindrome or not.
3. Identical strings: If a and b are identical, the function will return True because any split will result in a palindrome.
4. Palindrome strings: If a or b is already a palindrome, the function will correctly return True because we can choose an empty prefix for one string and the entire other string as the suffix.