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.

#1616

Medium

auto_awesome双·指针·invariant

LeetCode 题解工作台

分割两个字符串得到回文串

给你两个字符串 a 和 b ，它们长度相同。请你选择一个下标，将两个字符串都在相同的下标分割开。由 a 可以得到两个字符串： a prefix 和 a suffix ，满足 a = a prefix + a suffix ，同理，由 b 可以得到两个字符串 b prefix 和 b suffix…

双指针字符串

题目描述

给你两个字符串 a 和 b ，它们长度相同。请你选择一个下标，将两个字符串都在 相同的下标 分割开。由 a 可以得到两个字符串： a_prefix 和 a_suffix ，满足 a = a_prefix + a_suffix，同理，由 b 可以得到两个字符串 b_prefix 和 b_suffix ，满足 b = b_prefix + b_suffix 。请你判断 a_prefix + b_suffix 或者 b_prefix + a_suffix 能否构成回文串。

当你将一个字符串 s 分割成 s_prefix 和 s_suffix 时， s_suffix 或者 s_prefix 可以为空。比方说， s = "abc" 那么 "" + "abc" ， "a" + "bc" ， "ab" + "c" 和 "abc" + "" 都是合法分割。

如果 能构成回文字符串 ，那么请返回 true，否则返回 false 。

注意， x + y 表示连接字符串 x 和 y 。

示例 1：

输入：a = "x", b = "y"
输出：true
解释：如果 a 或者 b 是回文串，那么答案一定为 true ，因为你可以如下分割：
a_prefix = "", a_suffix = "x"
b_prefix = "", b_suffix = "y"
那么 a_prefix + b_suffix = "" + "y" = "y" 是回文串。

示例 2：

输入：a = "xbdef", b = "xecab"
输出：false

示例 3：

输入：a = "ulacfd", b = "jizalu"
输出：true
解释：在下标为 3 处分割：
a_prefix = "ula", a_suffix = "cfd"
b_prefix = "jiz", b_suffix = "alu"
那么 a_prefix + b_suffix = "ula" + "alu" = "ulaalu" 是回文串。

提示：

1 <= a.length, b.length <= 10⁵
a.length == b.length
a 和 b 都只包含小写英文字母

lightbulb

解题思路

方法一：双指针

我们可以使用双指针，其中一个指针 $i$ 从字符串 $a$ 的头部开始，另一个指针 $j$ 从字符串 $b$ 的尾部开始，如果两个指针指向的字符相等，那么两个指针同时往中间移动，直到遇到不同的字符或两指针交叉。

如果两指针交叉，即 $i \geq j$ ，说明 $prefix$ 和 $suffix$ 已经可以得到回文串，返回 true；否则，我们还需要判断 $a[i,...j]$ 或者 $b[i,...j]$ 是否是回文串，若是，返回 true。

否则，我们尝试交换两个字符串 $a$ 和 $b$ ，重复上述同样的过程。

时间复杂度 $O(n)$ ，空间复杂度 $O(1)$ 。其中 $n$ 是字符串 $a$ 或 $b$ 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

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)

speed

复杂度分析

指标	值
时间	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.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

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

warning

常见陷阱

外企场景

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

swap_horiz

进阶变体

外企场景

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

help

常见问题

外企场景

继续练习

#1750 删除字符串两端相同字符后的最短长度 #1754 构造字典序最大的合并字符串 #1768 交替合并字符串