Problem Description

Given two strings a and b of the same length, you are allowed to split both strings at the same index (at any position from 0 up to the length of the string). After splitting, you can create a new string by combining the prefix of one string with the suffix of the other. Your task is to determine whether it is possible to split the strings in such a way that the resulting string is a palindrome.

Formally, for some index i (where 0 ≤ i ≤ len(a)), you can form two new strings:

• a[0:i] + b[i:]
• b[0:i] + a[i:]

Constraints:

• Both a and b have the same length.
• All characters are lowercase English letters.
• There is no restriction on reusing elements; the only constraint is splitting at the same index in both strings.

Thought Process

At first glance, the brute-force approach would be to try every possible split index and check if either a[0:i] + b[i:] or b[0:i] + a[i:] forms a palindrome. However, since checking all possible splits would be O(n) and checking if a string is a palindrome is also O(n), this would result in an O(n²) approach.

To optimize, we need to observe that once a mismatch is found between characters from the prefix of one string and the suffix of the other, we can check if the remaining substring (from the mismatch point) forms a palindrome in either of the original strings. This leads to a two-pointer approach where we compare characters from the outside in, switching to a direct palindrome check only when we find a mismatch.

This insight allows us to reduce unnecessary checks and avoid constructing new strings at every split. The problem then becomes: can we find a split point such that all mismatches can be resolved by a direct palindrome check on a substring?

Solution Approach

Let's break down the optimized solution step by step:

1. Two-pointer technique:
   • Use two pointers: left starting at 0 and right starting at the end of the string.
   • Compare a[left] with b[right] (and vice versa).
   • Continue moving inwards as long as the characters match.
2. Handle mismatch:
   • If a mismatch occurs, check if the remaining substring (from left to right) is a palindrome in either of the original strings (a or b).
   • This is because, up to the mismatch, the prefix and suffix are compatible; from the mismatch onward, we need a palindrome in one of the strings to complete the palindrome.
3. Check both combinations:
   • Since we can take prefix from a and suffix from b or vice versa, we need to check both a with b and b with a.
4. Palindrome helper:
   • Write a helper function to check if a substring is a palindrome using a simple two-pointer scan.
5. Return result:
   • If any of the checks succeed, return True; otherwise, return False.

This approach ensures we only scan each string a constant number of times, leading to a linear time solution.

Example Walkthrough

Example:
a = "xabcba", b = "ayxcba"

1. Start with left = 0, right = 5 (since length is 6).
2. Compare a[0] == b[5]: 'x' == 'a' → False.
3. Since they do not match, check if a[0:6] or b[0:6] is a palindrome.
   • a[0:6] = "xabcba" is not a palindrome ("x" != "a").
   • b[0:6] = "ayxcba" is not a palindrome ("a" != "a", but "y" != "b").
4. Now, try the other combination: compare b[0] == a[5]: 'a' == 'a' → True.
5. Move left to 1, right to 4.
6. Compare b[1] == a[4]: 'y' == 'b' → False.
7. Check if b[1:5] or a[1:5] is palindrome.
   • b[1:5] = "yxcb" is not a palindrome.
   • a[1:5] = "abcb" is not a palindrome.
8. Since all checks failed, return False.

If the strings were a = "ulacfd" and b = "jizalu", one of the splits would yield a palindrome ("jizalu" + "cfd" = "jizalucfd", which is not a palindrome, but "ulacfd" + "alu" = "ulacfdalu", which is a palindrome).

Time and Space Complexity

Brute-force approach:

• Try every split index (O(n)), and for each, check if the resulting string is a palindrome (O(n)).
• Total time complexity: O(n²).
• Space complexity: O(n) if concatenating substrings, O(1) otherwise.

• Use two pointers to scan from both ends in O(n) time.
• Only check for palindrome in substrings once per mismatch, which is O(n).
• Total time complexity: O(n).
• Space complexity: O(1) (no extra data structures needed).

Summary

The key insight in this problem is that we don't need to check every possible split exhaustively. Instead, we can use a two-pointer approach to compare corresponding characters from the prefix of one string and the suffix of the other. If a mismatch is found, we only need to check if the remaining substring forms a palindrome in one of the original strings. This dramatically reduces the number of checks needed and makes the solution efficient and elegant.

This strategy leverages the properties of palindromes and string manipulation, making it a great example of optimizing brute-force approaches using two-pointer techniques.

Code Implementation

class Solution:
    def checkPalindromeFormation(self, a: str, b: str) -> bool:
        def is_palindrome(s, l, r):
            while l < r:
                if s[l] != s[r]:
                    return False
                l += 1
                r -= 1
            return True

        def check(a, b):
            l, r = 0, len(a) - 1
            while l < r and a[l] == b[r]:
                l += 1
                r -= 1
            return is_palindrome(a, l, r) or is_palindrome(b, l, r)

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

class Solution {
public:
    bool isPalindrome(const string& s, int l, int r) {
        while (l < r) {
            if (s[l] != s[r]) return false;
            ++l;
            --r;
        }
        return true;
    }

    bool check(const string& a, const string& b) {
        int l = 0, r = a.size() - 1;
        while (l < r && a[l] == b[r]) {
            ++l;
            --r;
        }
        return isPalindrome(a, l, r) || isPalindrome(b, l, r);
    }

    bool checkPalindromeFormation(string a, string b) {
        return check(a, b) || check(b, a);
    }
};
      

class Solution {
    private boolean isPalindrome(String s, int l, int r) {
        while (l < r) {
            if (s.charAt(l) != s.charAt(r)) return false;
            l++;
            r--;
        }
        return true;
    }

    private boolean check(String a, String b) {
        int l = 0, r = a.length() - 1;
        while (l < r && a.charAt(l) == b.charAt(r)) {
            l++;
            r--;
        }
        return isPalindrome(a, l, r) || isPalindrome(b, l, r);
    }

    public boolean checkPalindromeFormation(String a, String b) {
        return check(a, b) || check(b, a);
    }
}
      

var checkPalindromeFormation = function(a, b) {
    function isPalindrome(s, l, r) {
        while (l < r) {
            if (s[l] !== s[r]) return false;
            l++;
            r--;
        }
        return true;
    }
    function check(a, b) {
        let l = 0, r = a.length - 1;
        while (l < r && a[l] === b[r]) {
            l++;
            r--;
        }
        return isPalindrome(a, l, r) || isPalindrome(b, l, r);
    }
    return check(a, b) || check(b, a);
};