Split Two Strings to Make Palindrome
MedPrompt
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: falseExample 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
Approaches
2 approaches with complexity analysis and trade-offs.
The brute-force approach systematically checks every possible way to split the strings. It iterates through all n+1 potential split points. At each point, it constructs the two possible combined strings, a_prefix + b_suffix and b_prefix + a_suffix, and then checks if either of them is a palindrome. While straightforward, this method is computationally expensive.
Algorithm
- Iterate through every possible split index
ifrom0ton, wherenis the length of the strings. - For each index
i:- Create the four substrings:
a_prefix = a.substring(0, i),a_suffix = a.substring(i),b_prefix = b.substring(0, i), andb_suffix = b.substring(i). - Form two new strings:
s1 = a_prefix + b_suffixands2 = b_prefix + a_suffix. - Check if
s1is a palindrome using a helper function. - If
s1is a palindrome, returntrueimmediately. - Check if
s2is a palindrome. - If
s2is a palindrome, returntrueimmediately.
- Create the four substrings:
- If the loop completes without finding any palindrome, return
false.
Walkthrough
This method involves a loop that runs from i = 0 to n (inclusive), where n is the length of the strings. The index i represents the point where the split occurs. For each i, we generate a_prefix and b_prefix (from the start of the strings up to i-1) and a_suffix and b_suffix (from index i to the end). Then, we concatenate them to form a_prefix + b_suffix and b_prefix + a_suffix. A helper function isPalindrome is used to check these new strings. If a palindrome is found at any step, we can immediately conclude the answer is true. If we exhaust all possible splits without success, the answer is false.
class Solution { public boolean checkPalindromeFormation(String a, String b) { int n = a.length(); for (int i = 0; i <= n; i++) { String a_prefix = a.substring(0, i); String a_suffix = a.substring(i); String b_prefix = b.substring(0, i); String b_suffix = b.substring(i); if (isPalindrome(a_prefix + b_suffix)) { return true; } if (isPalindrome(b_prefix + a_suffix)) { return true; } } return false; } private boolean isPalindrome(String s) { int left = 0; int right = s.length() - 1; while (left < right) { if (s.charAt(left) != s.charAt(right)) { return false; } left++; right--; } return true; }}Complexity
Time
O(N^2). The loop runs N+1 times. Inside the loop, string slicing, concatenation, and palindrome checking each take O(N) time, leading to a total complexity of O(N * N).
Space
O(N), where N is the length of the strings. This space is used to store the newly created concatenated strings inside the loop.
Trade-offs
Pros
Simple to conceptualize and implement.
Correctly solves the problem for small inputs.
Cons
Highly inefficient due to repeated work.
String slicing and concatenation in a loop are expensive operations.
Will likely result in a 'Time Limit Exceeded' error for large inputs as specified in the constraints.
A more efficient solution uses a greedy two-pointer approach. Instead of building and checking strings for every split, we can determine if a valid split is possible in linear time. The core idea is to check the two main possibilities (a_prefix + b_suffix and b_prefix + a_suffix) by matching characters from the outside in. When a mismatch occurs, we only need to check if the remaining central part of either string is a palindrome.
Algorithm
- The main function
checkPalindromeFormationchecks two symmetric cases:check(a, b)andcheck(b, a). If either returnstrue, the result istrue. - The helper function
check(s1, s2)determines ifs1_prefix + s2_suffixcan form a palindrome. - Inside
check(s1, s2):- Use two pointers,
leftstarting at0andrightatn-1. - Greedily match the outer characters: while
left < rightands1.charAt(left) == s2.charAt(right), incrementleftand decrementright. - This loop finds the longest prefix of
s1that matches the reverse of a suffix ofs2. - After the loop, the outer parts of a potential palindrome are confirmed. The remaining middle part, from index
lefttoright, must also be a palindrome. - This middle part can be formed either by the substring from
s1(s1[left...right]) or the substring froms2(s2[left...right]). - Check if
isPalindrome(s1, left, right)orisPalindrome(s2, left, right)is true. Return the result of this logical OR.
- Use two pointers,
- The
isPalindrome(s, left, right)helper function checks if a substring is a palindrome in O(N) time without creating a new string.
Walkthrough
Let's analyze the condition for a_prefix + b_suffix to be a palindrome. We can define a helper function, check(s1, s2), that verifies if a prefix of s1 concatenated with a suffix of s2 can form a palindrome. The final answer would be check(a, b) || check(b, a).
Inside check(s1, s2), we use two pointers, left at the beginning and right at the end. We move them inwards as long as s1.charAt(left) equals s2.charAt(right). This greedily finds the longest prefix of s1 that matches the reverse of s2's suffix.
When the pointers stop at indices left and right (because s1.charAt(left) != s2.charAt(right) or left >= right), the outer portion of our potential palindrome is already valid. The problem reduces to checking if the inner part, corresponding to the substring from left to right, can form a palindrome. This inner part can be taken entirely from s1 (i.e., s1.substring(left, right + 1)) or entirely from s2 (i.e., s2.substring(left, right + 1)). If either of these substrings is a palindrome, we have found a valid split. If left >= right when the loop terminates, it means the entire string can be formed into a palindrome (as the middle part is empty or a single character, which is always a palindrome), so the check will pass.
This approach avoids expensive string manipulations and re-computations, achieving a linear time complexity.
class Solution { public boolean checkPalindromeFormation(String a, String b) { return check(a, b) || check(b, a); } private boolean check(String s1, String s2) { int n = s1.length(); int left = 0; int right = n - 1; while (left < right && s1.charAt(left) == s2.charAt(right)) { left++; right--; } // If pointers crossed or met, it's a palindrome. if (left >= right) { return true; } // Check if the middle part of either string is a palindrome. return isPalindrome(s1, left, right) || isPalindrome(s2, left, right); } private boolean isPalindrome(String s, int left, int right) { while (left < right) { if (s.charAt(left) != s.charAt(right)) { return false; } left++; right--; } return true; }}Complexity
Time
O(N), where N is the length of the strings. The `check` function performs a single pass with two pointers and then up to two palindrome checks on the remaining substring. Each of these operations takes at most O(N) time. Since this is done a constant number of times, the overall complexity is linear.
Space
O(1). The algorithm uses a fixed number of variables for pointers, regardless of the input size.
Trade-offs
Pros
Optimal time complexity.
Efficient in terms of space, using only a constant amount of extra memory.
Cons
The logic is more subtle and can be harder to come up with during an interview compared to the brute-force method.
Solutions
Solution
class Solution {public boolean checkPalindromeFormation(String a, String b) { return check1(a, b) || check1(b, a); }private boolean check1(String a, String b) { int i = 0; int j = b.length() - 1; while (i < j && a.charAt(i) == b.charAt(j)) { i++; j--; } return i >= j || check2(a, i, j) || check2(b, i, j); }private boolean check2(String a, int i, int j) { while (i < j && a.charAt(i) == a.charAt(j)) { i++; j--; } return i >= j; }}class Solution {public: bool checkPalindromeFormation(string a, string b) { return check1(a, b) || check1(b, a); } private: bool check1(string &a, string &b) { int i = 0, j = b.size() - 1; while (i < j && a[i] == b[j]) { ++i; --j; } return i >= j || check2(a, i, j) || check2(b, i, j); } bool check2(string &a, int i, int j) { while (i <= j && a[i] == a[j]) { ++i; --j; } return i >= j; }};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)Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.