Split Two Strings to Make Palindrome: Two-Pointer Pattern

You are given two strings a and b of the same length n. You pick a split index i from 0 to n. You form either a[:i] + b[i:] or b[:i] + a[i:]. Return true if either concatenation can produce a palindrome for some choice of i.

This is LeetCode 1616: Split Two Strings to Make Palindrome, and it is a clean application of the two-pointer technique to string matching. The trick is recognizing that you do not need to try every possible split index.

Why this problem matters

Palindrome problems show up constantly in interviews. Most of them boil down to some form of two-pointer comparison, either from the outside inward or from the center outward. This problem adds a twist: you are combining pieces of two different strings instead of checking a single string. That forces you to think carefully about what "matching" means when the characters come from different sources.

The pattern you learn here, using two pointers to match characters from opposite ends of different strings, then falling back to a single-string palindrome check for the middle, transfers directly to problems involving string transformations, partitioning, and hybrid palindrome construction.

The key insight

If you try every split index from 0 to n and check each concatenation, you get O(n^2) time. That is too slow. The key insight is that you can use two pointers from outside inward.

Start with left = 0 and right = n - 1. Compare a[left] with b[right]. As long as they match, they form the outer "shell" of a palindrome, and you move left forward and right backward. When they stop matching (or the pointers cross), the remaining middle portion from index left to right must itself be a palindrome, and it can come entirely from either a or b.

You run this procedure twice: once comparing a[left] vs b[right], and once comparing b[left] vs a[right]. If either ordering produces a valid palindrome, return true.

The solution

def check_palindrome_formation(a: str, b: str) -> bool:
    def is_palindrome(s: str, left: int, right: int) -> bool:
        while left < right:
            if s[left] != s[right]:
                return False
            left += 1
            right -= 1
        return True

    def check(a: str, b: str) -> bool:
        left, right = 0, len(a) - 1
        while left < right and a[left] == b[right]:
            left += 1
            right -= 1
        return is_palindrome(a, left, right) or is_palindrome(b, left, right)

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

The is_palindrome helper checks whether a substring from index left to index right reads the same forwards and backwards. It uses the classic two-pointer palindrome check.

The check function does the main work. It starts two pointers at opposite ends and walks them inward, comparing a[left] against b[right]. Each matching pair means that character position is "covered" by the palindrome structure. When a mismatch occurs, the outer shell is locked in. The only question is whether the middle portion, from left to right, is a palindrome in either a or b. If yes, we can split at some index in that range and form a valid palindrome.

The top-level function tries both orderings: check(a, b) tests the prefix of a with the suffix of b, and check(b, a) tests the prefix of b with the suffix of a. If either works, return true.

Visual walkthrough

Let's trace through the algorithm with a = "abcdef" and b = "fedcba". Watch how the two pointers consume matching characters from opposite ends, then check the remaining middle.

In this example, the outer pointers matched all the way through before crossing. That means the entire concatenation at the split point is already a palindrome, and we return true without needing to check any middle substring.

Complexity analysis

Time is O(n) where n is the length of the strings. The outer two-pointer scan visits each index at most once. The inner palindrome check visits at most the remaining indices. Combined, each character is examined at most twice across both passes.

Space is O(1). The algorithm uses only a constant number of pointer variables. No extra strings or arrays are created.

The building blocks

1. Substring palindrome check

def is_palindrome(s, left, right):
    while left < right:
        if s[left] != s[right]:
            return False
        left += 1
        right -= 1
    return True

This is the fundamental palindrome building block. Two pointers start at opposite ends of a range and walk inward, comparing characters. If every pair matches, the substring is a palindrome. You see this exact helper in "Valid Palindrome" (LeetCode 125), "Longest Palindromic Substring" (LeetCode 5), and dozens of other palindrome problems. The parameterized version (taking left and right instead of always using 0 and len-1) makes it reusable for substrings.

2. Cross-string two-pointer matching

left, right = 0, len(a) - 1
while left < right and a[left] == b[right]:
    left += 1
    right -= 1

This is the novel piece. Instead of comparing characters within the same string, you compare a[left] against b[right]. The logic is the same as a palindrome check, but the characters come from two different strings. When the loop ends, left and right tell you how far the outer shell extends. This cross-string matching pattern appears in any problem where you combine parts of different sequences and need palindromic or symmetric structure.

Edge cases

• Already palindromic inputs: if a or b is already a palindrome, the answer is always true (split at i = 0 or i = n).
• Single character strings: n = 1. Any single character is a palindrome. Return true.
• Identical strings: if a == b and a is a palindrome, return true. If a == b and a is not a palindrome, you still need to check whether some split produces one.
• Completely mismatched outer characters: the outer loop exits immediately at left = 0, and you fall back to checking whether a[0..n-1] or b[0..n-1] is itself a palindrome.
• All same characters: e.g., a = "aaaa", b = "aaaa". Every split produces a palindrome. Return true.

From understanding to recall

You have seen how two pointers from opposite ends can efficiently determine whether two strings can be split and recombined into a palindrome. The logic is compact: match the outer shell across strings, then check the middle within one string. But writing it correctly under pressure, remembering to try both orderings, remembering to check both a and b for the middle, these are recall challenges.

Spaced repetition is how you lock this in. You practice the cross-string two-pointer loop and the parameterized palindrome check from memory at increasing intervals. After a few rounds, the pattern is automatic. You see "split two strings" in a problem description, and the two-pointer template flows out without hesitation.

Related posts

• Valid Palindrome - The foundational two-pointer palindrome check that this problem builds on
• Longest Palindromic Substring - Expand-from-center palindrome detection, a complementary technique
• Two Sum - Another classic two-pointer pattern where pointers converge from opposite ends

CodeBricks breaks Split Two Strings to Make Palindrome into its cross-string matching and substring palindrome check building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a palindrome problem shows up in your interview, you do not think about it. You just write it.