Split Two Strings to Make Palindrome

Split Two Strings to Make Palindrome

What is this problem about?

In the Split Two Strings to Make Palindrome interview question, you are given two strings $a$ and $b$ of the same length. You need to check if there exists an index $i$ such that either $a_{prefix} + b_{suffix}$ or $b_{prefix} + a_{suffix}$ forms a palindrome. The split must happen at the same index for both strings.

Why is this asked in interviews?

This is a classic Google interview question that tests your proficiency with the Two Pointers interview pattern and your ability to identify symmetry. It requires a clean, modular approach to avoid redundant code and handle the logic for both $a_{prefix} + b_{suffix}$ and $b_{prefix} + a_{suffix}$ efficiently.

Algorithmic pattern used

The algorithm uses the Two Pointers technique. You compare the characters of $a$ from the start and $b$ from the end. As long as they match, you move the pointers inward. When you find a mismatch at indices $l$ and $r$, the only way to form a palindrome is if the remaining middle portion of either string $a$ or string $b$ (from $l$ to $r$) is itself a palindrome.

Example explanation (use your own example)

Let $a = "abcde"$ and $b = "fghba"$.

1. Compare $a[0]$ ('a') and $b[4]$ ('a'). They match.
2. Compare $a[1]$ ('b') and $b[3]$ ('b'). They match.
3. Compare $a[2]$ ('c') and $b[2]$ ('h'). Mismatch! Now, check if the middle of $a$ ("c") or the middle of $b$ ("h") is a palindrome. Both are! So, $a_{prefix} + b_{suffix}$ (where we take "ab" from $a$ and "hba" from $b$) results in "abhba", which is a palindrome.

Common mistakes candidates make

• Brute Force: Trying every possible split point, which leads to $O(N^2)$ and a Time Limit Exceeded error.
• Missing the "other" case: Only checking $a_{prefix} + b_{suffix}$ and forgetting $b_{prefix} + a_{suffix}$.
• Complex logic: Writing one giant function instead of a helper function to check if a substring is a palindrome.
• Off-by-one errors: Incorrectly calculating the indices for the middle substring check.

Interview preparation tip

Always look for ways to reuse code. In this Split Two Strings to Make Palindrome coding problem, the logic for both combinations is nearly identical. Write a generic function that takes two strings and checks the condition, then call it twice with the arguments swapped.