Split Two Strings to Make Palindrome - Solution & Explanation
Problem Statement
You are given two strings a and b of the same length. Choose an index and split both strings at the same index, splitting a into two strings: aprefix and asuffix where a = aprefix + asuffix, and splitting b into two strings: bprefix and bsuffix where b = bprefix + bsuffix. Check if aprefix + bsuffix or bprefix + asuffix forms a palindrome.
When you split a string s into sprefix and ssuffix, either ssuffix or sprefix is allowed to be empty. For example, if s = "abc", then "" + "abc", "a" + "bc", "ab" + "c" , and "abc" + "" are valid splits.
Return true if it is possible to form a palindrome string, otherwise return false.
Notice that x + y denotes the concatenation of strings x and y.
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 2:
Input: a = "xbdef", b = "xecab" Output: false
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.
Constraints:
1 <= a.length, b.length <= 105a.length == b.lengthaandbconsist of lowercase English letters
Approach Overview
Problem Overview: You are given two strings a and b of equal length. You can split both strings at the same index and combine one prefix with the other suffix. The goal is to determine whether any such split forms a palindrome.
Approach 1: Recursive Backtracking (O(n^2) time, O(n) space)
A straightforward way is to try every possible split index. For each index i, form two candidate strings: a[0..i] + b[i+1..n-1] and b[0..i] + a[i+1..n-1]. After building each candidate, check whether it is a palindrome by comparing characters from both ends. Backtracking or recursive exploration can simulate all split combinations while validating palindrome structure. This approach is useful for understanding the problem constraints, but it performs redundant palindrome checks, leading to O(n^2) time in the worst case.
Approach 2: Two Pointer Technique (O(n) time, O(1) space)
The optimal strategy relies on the observation that only the middle mismatch region matters. Start with two pointers: one at the beginning of a and one at the end of b. Move both pointers inward while characters match (a[left] == b[right]). Once a mismatch appears, the remaining substring must already be a palindrome in either a or b. At that point, run a standard palindrome check on a[left..right] or b[left..right]. Repeat the same process with the roles of the strings reversed (b prefix with a suffix). Each pointer moves at most n steps and the palindrome check runs once, keeping the total complexity linear.
This works because any valid split must preserve the mirrored characters on the outside. Once the outside matches are validated, only one continuous substring remains uncertain. If that substring is already a palindrome in either string, the combined result also becomes a palindrome.
The technique heavily relies on the two pointers pattern and efficient substring comparison. Understanding how mismatches limit the search space is the key insight. The palindrome verification itself is just a symmetric comparison commonly used in string problems.
Recommended for interviews: The Two Pointer approach is what interviewers expect. It reduces the brute force O(n^2) search to O(n) by exploiting palindrome symmetry. Discussing the brute force idea briefly shows problem exploration, but implementing the linear-time pointer solution demonstrates strong algorithmic reasoning and familiarity with common two pointer patterns.
Approach 1: Two Pointer Technique
The main idea is to check every possible split of the strings and verify if either `a_prefix + b_suffix` or `b_prefix + a_suffix` forms a palindrome. We will use the two-pointer technique for efficient palindrome checking by keeping two pointers, one starting from the beginning and the other starting from the end. If the characters don't match, we will allow switching to check cross-over sections between the two strings. If at any point they form a palindrome, return `true`; otherwise, try the next possible crossover. Use two modal checks: one keeping `a_prefix + b_suffix` and the other for `b_prefix + a_suffix`.
This C solution uses a helper function `is_palindrome` to determine if a substring is a palindrome. It checks both possible palindrome formations, `a_prefix + b_suffix` and `b_prefix + a_suffix`, using a two-pointer technique to traverse from both ends of the strings towards the middle. The switch between the strings happens when characters start to mismatch, checking for both combinations. The code employs `strlen` for length calculation and simple pointer manipulation for efficiency.
Complexity
Time Complexity: O(n), where n is the length of the strings. Each iteration moves the pointers inward and performs constant-time checks.
Space Complexity: O(1), no extra space used apart from input size.
Approach 2: Recursive Backtracking
This approach seeks palindrome formation by recursively attempting splits of the strings at different indexes and checking possible palindromes with helper recursion and backtracking. Each function call will handle a subproblem of checking a specific segment or crossover between strings. Although recursive backtracking is naturally less efficient for this problem size, it provides a profound uncluttered view of examining different options step-by-step via recursion.
In this C solution, the recursive helper `is_palindrome` checks if a substring segment forms a palindrome, addressing subproblems progressively via recursion. Main function `check_palindrome_formation_recursive` inspects crossovers and checks if recursive conditions yield palindromes, identifying valid paths. Despite potential inefficiencies due to recursion depth, it gives a hands-on approach to verifying combinatorial options.
Complexity
Time Complexity: O(n), efficient combination checks recognizing palindromes recursively.
Space Complexity: O(n) due to call stack depth with recursion.
Approach 3: 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.
If the two pointers cross, i.e., i geq j, it means that prefix and suffix can already form a palindrome, and we return true. Otherwise, we need to check if a[i,...j] or b[i,...j] is a palindrome. If so, return true.
Otherwise, we try swapping the two strings a and b and repeat the same process.
The time complexity is O(n), and the space complexity is O(1). Where n is the length of string a or b.
Complexity Comparison
| Approach | Complexity |
|---|---|
| Two Pointer Technique | Time Complexity: O(n), where n is the length of the strings. Each iteration moves the pointers inward and performs constant-time checks. |
| Recursive Backtracking | Time Complexity: O(n), efficient combination checks recognizing palindromes recursively. |
| Two Pointers | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive Backtracking | O(n^2) | O(n) | Good for understanding all split possibilities or explaining brute force reasoning during interviews |
| Two Pointer Technique | O(n) | O(1) | Optimal solution for interviews and production; minimizes comparisons by checking mismatch boundaries |
Video Solution
split two strings to make palindrome | leetcode 1616 | two pointer | string | palindrome • Naresh Gupta • 5,840 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Split Two Strings to Make Palindrome easy or hard?
How to solve Split Two Strings to Make Palindrome in O(n)?
Split Two Strings to Make Palindrome Python or Java solution
What is the best approach for Split Two Strings to Make Palindrome?
Is Split Two Strings to Make Palindrome asked at Google/Amazon/Meta?
What data structure is used in Split Two Strings to Make Palindrome?
What is the time complexity of Split Two Strings to Make Palindrome?
Ready to solve this problem?
Practice Split Two Strings to Make Palindrome with our built-in code editor and test cases.
Practice on FleetCode