LeetCode 1616 - Split Two Strings to Make Palindrome

This problem gives us two strings, a and b, both having the same length. We are allowed to choose a split index and divi

leetcodemediumtwo-pointersstring

LeetCode Problem 1616

Difficulty: 🟡 Medium
Topics: Two Pointers, String

Solution

Problem Understanding

This problem gives us two strings, a and b, both having the same length. We are allowed to choose a split index and divide both strings at exactly the same position.

If we split:

  • a into aprefix + asuffix
  • b into bprefix + bsuffix

then we may form two candidate strings:

  • aprefix + bsuffix
  • bprefix + asuffix

The task is to determine whether at least one of these combinations can become a palindrome.

A palindrome is a string that reads the same forward and backward.

The important detail is that the split can occur anywhere, including the boundaries of the string. That means one side of the split may be empty. For example:

  • split at index 0
  • split at index n

are both valid.

The constraints are very important:

  • 1 <= n <= 10^5
  • only lowercase English letters
  • both strings have equal length

A length of 10^5 immediately tells us that quadratic solutions are too slow. Any approach that tries every split and reconstructs strings repeatedly will likely exceed time limits. We need something close to linear time.

Several edge cases are important:

  • Single character strings are always valid because every single character string is a palindrome.
  • One of the original strings may already be a palindrome.
  • The valid palindrome may only appear after mixing the two strings.
  • Mismatches may occur very early or very late in the strings.
  • The split could happen at the beginning or end, meaning we may effectively choose only one original string.

The problem guarantees:

  • Both strings have equal length.
  • Strings contain only lowercase English letters.
  • Length is at least 1, so empty input never occurs.

Approaches

Brute Force Approach

The brute force solution tries every possible split index.

For every split position i:

  • Build a[:i] + b[i:]
  • Build b[:i] + a[i:]
  • Check whether either result is a palindrome

Palindrome checking itself costs O(n), and there are n + 1 possible split positions.

Therefore:

  • Constructing and checking each candidate costs O(n)
  • We do this O(n) times

This leads to O(n^2) time complexity.

With n = 10^5, this becomes far too slow.

Key Insight for the Optimal Solution

A palindrome only fails when characters at mirrored positions differ.

Suppose we try to form:

a prefix + b suffix

We compare:

  • left side from a
  • right side from b

using two pointers:

  • left starts at beginning
  • right starts at end

As long as:

a[left] == b[right]

the palindrome condition still holds.

Eventually one of two things happens:

  1. We finish successfully
  2. We encounter the first mismatch

At the first mismatch, we no longer have freedom to keep mixing arbitrarily. The remaining middle section must already be a palindrome entirely inside one string.

So after the mismatch, we only need to check:

  • Is a[left:right+1] a palindrome?
  • OR is b[left:right+1] a palindrome?

If either is true, then a valid split exists.

This observation reduces the problem from trying every split independently to a single linear scan.

We must test both directions:

  • a prefix + b suffix
  • b prefix + a suffix

because either arrangement may succeed.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(n) Try every split and construct candidate strings
Optimal O(n) O(1) Two pointer scan with palindrome verification

Algorithm Walkthrough

  1. Define a helper function is_palindrome(s, left, right).

This function checks whether the substring s[left:right+1] is a palindrome using two pointers moving inward. 2. Define another helper function check(x, y).

This function tests whether combining:

x prefix + y suffix

can form a palindrome. 3. Inside check(x, y), initialize:

  • left = 0
  • right = len(x) - 1
  1. Move the pointers inward while:
x[left] == y[right]

This means the outer characters still satisfy palindrome symmetry. 5. Stop at the first mismatch.

At this point, the remaining middle section must come entirely from one string. 6. Check whether either remaining substring is already a palindrome:

  • x[left:right+1]
  • y[left:right+1]

If either is a palindrome, return True. 7. If the entire scan completes without mismatch, return True.

This means the mixed string already satisfies palindrome symmetry completely. 8. Run:

check(a, b)

and

check(b, a)
  1. If either succeeds, return True. Otherwise return False.

Why it works

The algorithm relies on the fact that palindrome validity depends only on mirrored character pairs.

While scanning from the outside inward, we are effectively deciding which parts come from which string. Once the first mismatch occurs, no further mixing can repair the mismatch pattern. The only possibility is that the remaining middle section already forms a palindrome entirely within one string.

Therefore checking the remaining substring inside either original string is sufficient and guarantees correctness.

Python Solution

class Solution:
    def checkPalindromeFormation(self, 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(x: str, y: str) -> bool:
            left = 0
            right = len(x) - 1

            while left < right and x[left] == y[right]:
                left += 1
                right -= 1

            return (
                is_palindrome(x, left, right)
                or is_palindrome(y, left, right)
            )

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

The implementation starts with the is_palindrome helper, which performs a standard two pointer palindrome check on a substring. This avoids creating new strings and keeps memory usage constant.

The check helper performs the main logic. It compares the left side of one string against the right side of the other string. As long as characters match, the mixed palindrome remains valid.

When a mismatch appears, the algorithm checks whether the remaining middle portion is already a palindrome within either original string. If so, we can choose the split at exactly that location.

Finally, the solution checks both possible concatenation directions because either arrangement may produce the palindrome.

Go Solution

func checkPalindromeFormation(a string, b string) bool {
	isPalindrome := func(s string, left int, right int) bool {
		for left < right {
			if s[left] != s[right] {
				return false
			}
			left++
			right--
		}
		return true
	}

	var check func(string, string) bool

	check = func(x string, y string) bool {
		left := 0
		right := len(x) - 1

		for left < right && x[left] == y[right] {
			left++
			right--
		}

		return isPalindrome(x, left, right) ||
			isPalindrome(y, left, right)
	}

	return check(a, b) || check(b, a)
}

The Go implementation closely mirrors the Python version.

Strings in Go are indexed by bytes, which is safe here because the input contains only lowercase English letters. No Unicode handling is required.

The helper functions use closures for cleaner organization. Memory usage remains constant because no substring copies are created.

Worked Examples

Example 1

a = "x"
b = "y"

Since the length is 1, every single character string is already a palindrome.

Running check(a, b):

left right condition
0 0 loop stops immediately

Now check:

  • "x" palindrome → true
  • "y" palindrome → true

Result:

true

Example 2

a = "xbdef"
b = "xecab"

Check a prefix + b suffix.

left right a[left] b[right] match
0 4 x b no

Mismatch occurs immediately.

Now check remaining substrings:

a = "xbdef"
b = "xecab"

Neither is a palindrome.

Now try the opposite direction.

Check b prefix + a suffix.

left right b[left] a[right] match
0 4 x f no

Again, immediate mismatch.

Neither remaining substring is a palindrome.

Result:

false

Example 3

a = "ulacfd"
b = "jizalu"

Check a prefix + b suffix.

left right a[left] b[right] match
0 5 u u yes
1 4 l l yes
2 3 a a yes

Pointers cross successfully.

This means:

"ula" + "alu" = "ulaalu"

which is a palindrome.

Result:

true

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each pointer moves inward at most once
Space O(1) Only a few variables are used

The algorithm performs at most a constant number of linear scans across the strings. Each helper function processes characters using two pointers without allocating additional data structures. Therefore the runtime is linear and the extra memory usage is constant.

Test Cases

solution = Solution()

assert solution.checkPalindromeFormation("x", "y") == True
# Single character strings

assert solution.checkPalindromeFormation("xbdef", "xecab") == False
# No valid split exists

assert solution.checkPalindromeFormation("ulacfd", "jizalu") == True
# Mixed palindrome exists

assert solution.checkPalindromeFormation("abdef", "fecab") == True
# Valid palindrome after split

assert solution.checkPalindromeFormation("abcdef", "fedcba") == True
# Entire mixed string forms palindrome

assert solution.checkPalindromeFormation("aaaa", "bbbb") == True
# Repeated characters

assert solution.checkPalindromeFormation("abc", "def") == False
# Completely incompatible strings

assert solution.checkPalindromeFormation("race", "ecar") == True
# One direction succeeds immediately

assert solution.checkPalindromeFormation("aab", "baa") == True
# Palindrome formed near middle

assert solution.checkPalindromeFormation("abcc", "cbaa") == True
# Requires checking remaining substring

assert solution.checkPalindromeFormation("abcdxy", "yxdcba") == True
# Long symmetric crossing

assert solution.checkPalindromeFormation("abcxy", "yxdef") == False
# Mismatch with non-palindrome remainder

Test Summary

Test Why
"x", "y" Smallest possible input
"xbdef", "xecab" No valid palindrome formation
"ulacfd", "jizalu" Standard successful mixed palindrome
"abdef", "fecab" Valid split inside strings
"abcdef", "fedcba" Entire crossing matches
"aaaa", "bbbb" Repeated characters
"abc", "def" Fully incompatible strings
"race", "ecar" Opposite direction succeeds
"aab", "baa" Odd length palindrome behavior
"abcc", "cbaa" Remaining substring palindrome
"abcdxy", "yxdcba" Longer successful matching
"abcxy", "yxdef" Failure after mismatch

Edge Cases

Single Character Strings

When both strings contain only one character, the answer is always true. Any single character string is inherently a palindrome. A naive implementation might incorrectly assume a split is necessary, but the problem allows empty prefixes and suffixes. The implementation handles this naturally because the two pointer loop immediately terminates and the substring palindrome check succeeds.

Mismatch at the First Character

Cases like:

a = "abc"
b = "xyz"

fail immediately at the outermost comparison. A buggy implementation might continue searching for another split unnecessarily. The optimal solution correctly recognizes that once the first mismatch occurs, only the remaining substring matters. Since neither remaining substring is a palindrome, the answer is correctly false.

One Original String Already Being a Palindrome

Suppose:

a = "racecar"
b = "abcdefg"

Even without mixing strings, the answer should be true because we may split at index 0 or n and effectively use only one string. The implementation handles this automatically because after mismatch detection, it checks whether either remaining substring is already a palindrome.