#1616

Medium

auto_awesomeTwo-pointer scanning with invariant tracking

LeetCode Problem Workspace

Split Two Strings to Make Palindrome

Determine if splitting two equal-length strings at a common index can form a palindrome using two-pointer scanning techniques.

two pointers string

Problem Statement

Given two strings a and b of the same length, split each string at the same index into a prefix and suffix. Determine whether concatenating aprefix with bsuffix or bprefix with asuffix produces a palindrome. The split can occur at any index, including at the ends, and either prefix or suffix can be empty.

Return true if any such split results in a palindrome string. Otherwise, return false. Constraints: strings consist of lowercase English letters, lengths up to 10^5, and both strings have identical lengths.

Examples

Example 1

Input: a = "x", b = "y"

Output: true Explaination: If either a or b are palindromes the answer is true since you can split in the following way: aprefix = "", asuffix = "x" bprefix = "", bsuffix = "y" Then, aprefix + bsuffix = "" + "y" = "y", which is a palindrome.

Example details omitted.

Example 2

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

Output: false

Example details omitted.

Example 3

Input: a = "ulacfd", b = "jizalu"

Output: true Explaination: Split them at index 3: aprefix = "ula", asuffix = "cfd" bprefix = "jiz", bsuffix = "alu" Then, aprefix + bsuffix = "ula" + "alu" = "ulaalu", which is a palindrome.

Example details omitted.

Constraints

1 <= a.length, b.length <= 105
a.length == b.length
a and b consist of lowercase English letters

Solution Approach

Two-Pointer Scanning for Prefix-Suffix Matching

Initialize two pointers at the start and end of the potential combined string. Move inward while characters match, tracking whether the current prefix from one string and suffix from the other can still form a palindrome.

Check Remaining Substrings Separately

If a mismatch occurs, verify if the remaining substring on either side is a palindrome on its own. This leverages the invariant that one side can complete the palindrome even if a full scan fails.

Return Early on Valid Combination

As soon as a valid palindrome combination is found using either prefix-suffix arrangement, return true. If all possible splits are exhausted without success, return false.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) per split check due to the two-pointer scan, but only up to two main checks are needed, yielding overall O(n). Space complexity is O(1) since no additional structures are required beyond pointers and loop variables.

What Interviewers Usually Probe

Look for a two-pointer solution rather than brute-force concatenation.
Early termination on palindrome detection shows understanding of invariants.
Attention to prefix-suffix mismatch handling indicates mastery of the problem pattern.

Common Pitfalls or Variants

Common pitfalls

Assuming all split positions must be checked fully rather than using two-pointer early termination.
Failing to handle empty prefix or suffix at string boundaries.
Not checking both a_prefix + b_suffix and b_prefix + a_suffix combinations for each split.

Follow-up variants

Strings containing uppercase letters or Unicode characters instead of lowercase English letters.
Allowing multiple splits with the sum of lengths from each string forming a palindrome.
Limiting splits to a specific index range or requiring fixed-length prefixes.

FAQ

What is the core pattern for 'Split Two Strings to Make Palindrome'?

The core pattern is two-pointer scanning with invariant tracking, combining a prefix from one string with a suffix from the other to form a palindrome.

Can either prefix or suffix be empty when splitting?

Yes, splits can occur at any index including at the ends, so empty prefixes or suffixes are valid.

Is it necessary to check both a_prefix + b_suffix and b_prefix + a_suffix?

Yes, both combinations must be checked at each split index to ensure all palindrome possibilities are covered.

What is the time complexity of this two-pointer approach?

Each two-pointer scan runs in O(n), and since only two main scans are required, the overall time complexity is O(n).

What common mistakes should I avoid when solving this problem?

Avoid checking every split naively, neglecting empty prefixes or suffixes, and forgetting to scan both prefix-suffix arrangements.

terminal

Solution

Solution 1: Two Pointers

We can use two pointers, where one pointer $i$ starts from the beginning of string $a$, and the other pointer $j$ starts from the end of string $b$. If the characters pointed to by the two pointers are equal, then both pointers move towards the center until they encounter different characters or the two pointers cross.

1

2

3

4

5

6

7

8

9

10

11

12

class Solution:
    def checkPalindromeFormation(self, a: str, b: str) -> bool:
        def check1(a: str, b: str) -> bool:
            i, j = 0, len(b) - 1
            while i < j and a[i] == b[j]:
                i, j = i + 1, j - 1
            return i >= j or check2(a, i, j) or check2(b, i, j)

        def check2(a: str, i: int, j: int) -> bool:
            return a[i : j + 1] == a[i : j + 1][::-1]

        return check1(a, b) or check1(b, a)

Continue Practicing

#1750 minimum length of string after deleting similar ends #1754 largest merge of two strings #1768 merge strings alternately