Split Two Strings to Make Palindrome - Video Solutions

Problem Overview: You are given two strings a and b of equal length. You can split both strings at the same index and combine one prefix with the other suffix. The goal is to determine whether any such split forms a palindrome.

Approach 1: Recursive Backtracking (O(n^2) time, O(n) space)

A straightforward way is to try every possible split index. For each index i, form two candidate strings: a[0..i] + b[i+1..n-1] and b[0..i] + a[i+1..n-1]. After building each candidate, check whether it is a palindrome by comparing characters from both ends. Backtracking or recursive exploration can simulate all split combinations while validating palindrome structure. This approach is useful for understanding the problem constraints, but it performs redundant palindrome checks, leading to O(n^2) time in the worst case.

Approach 2: Two Pointer Technique (O(n) time, O(1) space)

The optimal strategy relies on the observation that only the middle mismatch region matters. Start with two pointers: one at the beginning of a and one at the end of b. Move both pointers inward while characters match (a[left] == b[right]). Once a mismatch appears, the remaining substring must already be a palindrome in either a or b. At that point, run a standard palindrome check on a[left..right] or b[left..right]. Repeat the same process with the roles of the strings reversed (b prefix with a suffix). Each pointer moves at most n steps and the palindrome check runs once, keeping the total complexity linear.

This works because any valid split must preserve the mirrored characters on the outside. Once the outside matches are validated, only one continuous substring remains uncertain. If that substring is already a palindrome in either string, the combined result also becomes a palindrome.

The technique heavily relies on the two pointers pattern and efficient substring comparison. Understanding how mismatches limit the search space is the key insight. The palindrome verification itself is just a symmetric comparison commonly used in string problems.

Recommended for interviews: The Two Pointer approach is what interviewers expect. It reduces the brute force O(n^2) search to O(n) by exploiting palindrome symmetry. Discussing the brute force idea briefly shows problem exploration, but implementing the linear-time pointer solution demonstrates strong algorithmic reasoning and familiarity with common two pointer patterns.