Abstract / Summary

Check if you can split two strings into four parts so the first and last parts are reverses and the middle parts form a palindrome.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 33% (100k+ submissions).

Typical patterns to solve this problem:

• String
• Two Pointers

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided Solution class implements a method checkPalindromeFormation that determines whether two equal-length strings a and b can be combined, by taking a prefix from one and a suffix from the other, to form a palindrome. The algorithm explores both possible orientations-using a prefix from a with a suffix from b, and vice-versa-by delegating the core verification to an inner helper called deeper.

Core Logic

The entry point simply invokes the helper twice, swapping the arguments to cover both orientations:

return deeper(a, b) or deeper(b, a)

The helper deeper receives two strings x and y. It iterates from the outermost characters toward the centre, comparing the character at position left in x with the character at the mirrored position right in y. The loop is bounded by the length of the strings, stored in size.

for left in range(size):
    right = size - left - 1
    if left >= right:
        return True

When the two pointers cross (left >= right), every examined pair has matched, meaning the constructed string is already a palindrome, and the function returns True.

If a mismatch is encountered, the algorithm attempts to salvage the palindrome by checking whether the remaining inner segment of either x or y is itself a palindrome. The inner segment is defined by the current left and right indices:

if x[left] != y[right]:
    inner = x[left : right + 1]
    if inner == inner[::-1]:
        return True
    inner = y[left : right + 1]
    if inner == inner[::-1]:
        return True
    return False

The first inner slice extracts the substring of x that would become the middle part if we continue taking characters from x after the mismatch. If that slice reads the same forwards and backwards, the overall construction can be completed as a palindrome. The same check is performed for the corresponding slice of y. If neither slice forms a palindrome, the helper returns False, indicating that this orientation cannot yield a palindrome.

Edge Cases Handled

The algorithm gracefully handles the situation where the strings are already palindromic with respect to each other. In that case, the loop never encounters a mismatch, and the condition left >= right triggers a True return without any further work.

When the mismatch occurs at the very first pair of characters (left == 0), the inner slices become the full strings minus the outermost characters. The palindrome check on these slices still correctly determines whether the remaining portion can close the palindrome.

If the mismatch appears at the centre of an odd-length string, the inner slice reduces to a single character. Since any single character is trivially a palindrome, the check inner == inner[::-1] succeeds, allowing the function to return True. This covers the case where the two strings differ only at the central position.

When the strings have length one, the loop executes once, right becomes zero, and the left >= right condition is satisfied immediately, yielding True. Thus the method correctly handles the minimal input size.

Performance Optimizations

The implementation avoids unnecessary work by terminating the scan as soon as a definitive answer is known. The early exit on left >= right prevents further iteration once all required character pairs have been verified. Likewise, the immediate return after a successful inner palindrome check eliminates the need to continue scanning the remainder of the strings.

Using Python’s slice notation together with the built-in reverse comparison (inner[::-1]) provides an efficient, C-level palindrome test without constructing auxiliary data structures. This approach leverages the interpreter’s optimized handling of string slicing and reversal.

The helper is invoked only twice, covering both possible prefix-suffix orientations. No additional loops or recursion are introduced, keeping the runtime proportional to the length of the input strings while maintaining a low constant factor due to the minimal overhead of the inner palindrome checks.

Imagine two long chains of colorful toy blocks. Each block has a letter on it. A palindrome is a special type of chain where the letters read exactly the same way from the front as they do from the back, like the word radar.

The goal here is to snip the two chains at the same spot and glue the front of one chain to the back of the other. Once the pieces are joined, the task is to see if the new, combined chain is a perfect palindrome.

The code starts by looking at both chains block by block, starting from the opposite ends. As long as the letters match up perfectly, the process keeps moving toward the middle. If the letters stop matching, that is the spot where the chains get swapped. At that exact point, a smaller piece of the chain is checked to see if it is already a palindrome by itself. If either the front part from the first chain or the front part from the second chain can be joined with the back of the other to form a perfect palindrome, then the puzzle is solved. Both ways of joining the chains are tested to make sure no possibility is missed.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

not analyzed yet

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++		Python	Java				TS
	WalkCCC	C++		Python	Java
	leetcode.ca	C++		Python	Java		Go	Rust	TS
	Progiez	C++		Python	Java
github	black-shadows	C++
	charles-wangkai				Java
	everthis		JS
	fsq	C++
	JoshCrozier		JS
	keineahnung2345	C++
	lkwq007			Python
	suxrobGM					C#
	wisdompeak	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, Rust, TypeScript
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fsq	C++
JoshCrozier	JavaScript
keineahnung2345	C++
lkwq007	Python
suxrobGM	C#
wisdompeak	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality