Split Two Strings to Make Palindrome solution and explanation
Google
9 more videos on this problem
split two strings to make palindrome | leetcode 1616 | two pointer | string | palindromeNaresh Gupta · 10:54 · 5K views
花花酱 LeetCode 1616. Split Two Strings to Make Palindrome - 刷题找工作 EP361Hua Hua · 10:33 · 2K views
Split Two Strings to Make Palindrome Leetcode 1616 | leetcode solutionEasyLeetcode · 11:37 · 2K views
LeetCode 1616. Split Two Strings to Make PalindromeHappy Coding · 14:52 · 1K views
LeetCode 1616. Split Two Strings to Make Palindrome | Google Interview Question | PythonAH Tech · 6:39 · 1K views
1616. Split Two Strings to Make Palindrome (Leetcode Medium)Programming Live with Larry · 12:20 · 524 views
1616. Split Two Strings to Make PalindromeMuerde un zombie · 8:14 · 269 views
【每日一题】1616.Split Two Strings to Make Palindrome, 10/13/2020Huifeng Guan · 11:46 · 212 views
Split Two Strings to Make Palindrome | Javascript Solution | LeetcodeCode JS · 6:37 · 82 views
大壮刷题 - LeetCode 1616. Split Two Strings to Make Palindrome, Medium大壮刷题 · 7:38 · 72 views
The problem
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`.
def is_palindrome(s, left, right):
while left < right:
if s[left] != s[right]:
return False
left += 1
right -= 1
return True
def check_palindrome_formation(a, b):
n = len(a)
i, j = 0, n - 1
while i < j and a[i] == b[j]:
i += 1
j -= 1
if is_palindrome(a, i, j) or is_palindrome(b, i, j):
return True
i, j = 0, n - 1
while i < j and b[i] == a[j]:
i += 1
j -= 1
return is_palindrome(a, i, j) or is_palindrome(b, i, j)
if __name__ == "__main__":
a = "ulacfd"
b = "jizalu"
print(check_palindrome_formation(a, b)) # Output: Truepublic class Solution {
public boolean isPalindrome(String s, int left, int right) {
while (left < right) {
if (s.charAt(left) != s.charAt(right))
return false;
left++;
right--;
}
return true;
}
public boolean checkPalindromeFormation(String a, String b) {
int len = a.length();
int i = 0, j = len - 1;
while (i < j && a.charAt(i) == b.charAt(j)) {
i++;
j--;
}
if (isPalindrome(a, i, j) || isPalindrome(b, i, j))
return true;
i = 0; j = len - 1;
while (i < j && b.charAt(i) == a.charAt(j)) {
i++;
j--;
}
return isPalindrome(a, i, j) || isPalindrome(b, i, j);
}
public static void main(String[] args) {
Solution solution = new Solution();
String a = "ulacfd";
String b = "jizalu";
System.out.println(solution.checkPalindromeFormation(a, b)); // Output: true
}
}#include <iostream>
#include <string>
using namespace std;
bool isPalindrome(const string& s, int left, int right) {
while (left < right) {
if (s[left] != s[right]) return false;
left++;
right--;
}
return true;
}
bool checkPalindromeFormation(string a, string b) {
int len = a.size();
int i = 0, j = len - 1;
while (i < j && a[i] == b[j]) {
i++;
j--;
}
if (isPalindrome(a, i, j) || isPalindrome(b, i, j))
return true;
i = 0, j = len - 1;
while (i < j && b[i] == a[j]) {
i++;
j--;
}
return isPalindrome(a, i, j) || isPalindrome(b, i, j);
}
int main() {
string a = "ulacfd";
string b = "jizalu";
if (checkPalindromeFormation(a, b))
cout << "True" << endl;
else
cout << "False" << endl;
return 0;
}function isPalindrome(s, left, right) {
while (left < right) {
if (s[left] !== s[right]) {
return false;
}
left++;
right--;
}
return true;
}
function checkPalindromeFormation(a, b) {
const n = a.length;
let i = 0, j = n - 1;
while (i < j && a[i] === b[j]) {
i++;
j--;
}
if (isPalindrome(a, i, j) || isPalindrome(b, i, j)) {
return true;
}
i = 0;
j = n - 1;
while (i < j && b[i] === a[j]) {
i++;
j--;
}
return isPalindrome(a, i, j) || isPalindrome(b, i, j);
}
// Example usage:
const a = "ulacfd";
const b = "jizalu";
console.log(checkPalindromeFormation(a, b)); // Output: true#include <stdio.h>
#include <stdbool.h>
#include <string.h>
bool is_palindrome(const char* s, int left, int right) {
while (left < right) {
if (s[left] != s[right])
return false;
left++;
right--;
}
return true;
}
bool check_palindrome_formation(char* a, char* b) {
int len = strlen(a);
int i = 0, j = len - 1;
while (i < j && a[i] == b[j]) {
i++;
j--;
}
if (is_palindrome(a, i, j) || is_palindrome(b, i, j))
return true;
i = 0, j = len - 1;
while (i < j && b[i] == a[j]) {
i++;
j--;
}
return is_palindrome(a, i, j) || is_palindrome(b, i, j);
}
int main() {
char a[] = "ulacfd";
char b[] = "jizalu";
if (check_palindrome_formation(a, b))
printf("True\n");
else
printf("False\n");
return 0;
}using System;
class Solution {
public bool IsPalindrome(string s, int left, int right) {
while (left < right) {
if (s[left] != s[right])
return false;
left++;
right--;
}
return true;
}
public bool CheckPalindromeFormation(string a, string b) {
int n = a.Length;
int i = 0, j = n - 1;
while (i < j && a[i] == b[j]) {
i++;
j--;
}
if (IsPalindrome(a, i, j) || IsPalindrome(b, i, j))
return true;
i = 0; j = n - 1;
while (i < j && b[i] == a[j]) {
i++;
j--;
}
return IsPalindrome(a, i, j) || IsPalindrome(b, i, j);
}
static void Main() {
Solution solution = new Solution();
string a = "ulacfd";
string b = "jizalu";
Console.WriteLine(solution.CheckPalindromeFormation(a, b)); // Output: True
}
}This Python solution makes use of a function `is_palindrome` that checks if a string segment is a palindrome using a simple while loop to iterate from both ends of the substring until they meet or mismatch. The main function `check_palindrome_formation` checks each possible split with two pointers. It first examines `a_prefix + b_suffix` then reinitializes the pointers to look at `b_prefix + a_suffix`. This Python approach uses slicing and pointer manipulation to determine palindrome formations efficiently.
Time Complexity: O(n), where n is the length of strings, achieved by continual pointer adjustments.
Space Complexity: O(1), no extra space is used beyond temporary variables.
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.
def is_palindrome(s, left, right):
if left >= right:
return True
if s[left] != s[right]:
return False
return is_palindrome(s, left + 1, right - 1)
def check_palindrome_formation_recursive(a, b, left, right):
if left >= right:
return True
if a[left] == b[right]:
return check_palindrome_formation_recursive(a, b, left + 1, right - 1)
return is_palindrome(a, left, right) or is_palindrome(b, left, right)
def check_palindrome_formation(a, b):
return check_palindrome_formation_recursive(a, b, 0, len(a) - 1) or \
check_palindrome_formation_recursive(b, a, 0, len(b) - 1)
if __name__ == "__main__":
a = "ulacfd"
b = "jizalu"
print(check_palindrome_formation(a, b)) # Output: Truepublic class Solution {
public boolean isPalindrome(String s, int left, int right) {
if (left >= right) return true;
if (s.charAt(left) != s.charAt(right)) return false;
return isPalindrome(s, left + 1, right - 1);
}
public boolean checkPalindromeFormationRecursive(String a, String b, int left, int right) {
if(left >= right) return true;
if(a.charAt(left) == b.charAt(right))
return checkPalindromeFormationRecursive(a, b, left + 1, right - 1);
return isPalindrome(a, left, right) || isPalindrome(b, left, right);
}
public boolean checkPalindromeFormation(String a, String b) {
return checkPalindromeFormationRecursive(a, b, 0, a.length() - 1) ||
checkPalindromeFormationRecursive(b, a, 0, b.length() - 1);
}
public static void main(String[] args) {
Solution solution = new Solution();
String a = "ulacfd";
String b = "jizalu";
System.out.println(solution.checkPalindromeFormation(a, b)); // Output: true
}
}#include <iostream>
#include <string>
using namespace std;
bool isPalindrome(const string& s, int left, int right) {
if (left >= right) return true;
if (s[left] != s[right]) return false;
return isPalindrome(s, left + 1, right - 1);
}
bool checkPalindromeFormationRecursive(const string& a, const string& b, int left, int right) {
if (left >= right) return true;
if (a[left] == b[right])
return checkPalindromeFormationRecursive(a, b, left + 1, right - 1);
return isPalindrome(a, left, right) || isPalindrome(b, left, right);
}
bool checkPalindromeFormation(string a, string b) {
return checkPalindromeFormationRecursive(a, b, 0, a.length() - 1) ||
checkPalindromeFormationRecursive(b, a, 0, b.length() - 1);
}
int main() {
string a = "ulacfd";
string b = "jizalu";
cout << (checkPalindromeFormation(a, b) ? "True" : "False") << endl;
return 0;
}function isPalindrome(s, left, right) {
if (left >= right) return true;
if (s[left] !== s[right]) return false;
return isPalindrome(s, left + 1, right - 1);
}
function checkPalindromeFormationRecursive(a, b, left, right) {
if (left >= right) return true;
if (a[left] === b[right])
return checkPalindromeFormationRecursive(a, b, left + 1, right - 1);
return isPalindrome(a, left, right) || isPalindrome(b, left, right);
}
function checkPalindromeFormation(a, b) {
return checkPalindromeFormationRecursive(a, b, 0, a.length - 1) ||
checkPalindromeFormationRecursive(b, a, 0, b.length - 1);
}
// Example usage:
const a = "ulacfd";
const b = "jizalu";
console.log(checkPalindromeFormation(a, b)); // Output: true#include <stdio.h>
#include <stdbool.h>
#include <string.h>
bool is_palindrome(const char* s, int left, int right) {
if (left >= right) return true;
if (s[left] != s[right]) return false;
return is_palindrome(s, left + 1, right - 1);
}
bool check_palindrome_formation_recursive(char* a, char* b, int left, int right) {
if (left >= right) return true;
if (a[left] == b[right])
return check_palindrome_formation_recursive(a, b, left + 1, right - 1);
return is_palindrome(a, left, right) || is_palindrome(b, left, right);
}
bool check_palindrome_formation(char* a, char* b) {
return check_palindrome_formation_recursive(a, b, 0, strlen(a) - 1) ||
check_palindrome_formation_recursive(b, a, 0, strlen(b) - 1);
}
int main() {
char a[] = "ulacfd";
char b[] = "jizalu";
if (check_palindrome_formation(a, b))
printf("True\n");
else
printf("False\n");
return 0;
}using System;
class Solution {
public bool IsPalindrome(string s, int left, int right) {
if (left >= right) return true;
if (s[left] != s[right]) return false;
return IsPalindrome(s, left + 1, right - 1);
}
public bool CheckPalindromeFormationRecursive(string a, string b, int left, int right) {
if (left >= right) return true;
if (a[left] == b[right])
return CheckPalindromeFormationRecursive(a, b, left + 1, right - 1);
return IsPalindrome(a, left, right) || IsPalindrome(b, left, right);
}
public bool CheckPalindromeFormation(string a, string b) {
return CheckPalindromeFormationRecursive(a, b, 0, a.Length - 1) ||
CheckPalindromeFormationRecursive(b, a, 0, b.Length - 1);
}
static void Main() {
Solution solution = new Solution();
string a = "ulacfd";
string b = "jizalu";
Console.WriteLine(solution.CheckPalindromeFormation(a, b)); // Output: True
}
}In Python, the recursive technique revolves around helper functions that verify palindrome segments while `check_palindrome_formation_recursive` checks the cross-section between both strings. The recurrence base case analyzes whether segments turn into a palindrome, tackling deep recursion involving split and switch processes. This method encapsulates efficiency in recursive handling for valid palindrome splits.
Time Complexity: O(n), rapid cut through segments on recursion.
Space Complexity: O(n), depth-based stack recursion occupies space.
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.
function checkPalindromeFormation(a: string, b: string): boolean {
const check1 = (a: string, b: string) => {
let i = 0;
let 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);
};
const check2 = (a: string, i: number, j: number) => {
while (i < j && a.charAt(i) === a.charAt(j)) {
i++;
j--;
}
return i >= j;
};
return check1(a, b) || check1(b, a);
}func checkPalindromeFormation(a string, b string) bool {
return check1(a, b) || check1(b, a)
}
func check1(a, b string) bool {
i, j := 0, len(b)-1
for i < j && a[i] == b[j] {
i++
j--
}
return i >= j || check2(a, i, j) || check2(b, i, j)
}
func check2(a string, i, j int) bool {
for i < j && a[i] == a[j] {
i++
j--
}
return i >= j
}impl Solution {
pub fn check_palindrome_formation(a: String, b: String) -> bool {
fn check1(a: &[u8], b: &[u8]) -> bool {
let (mut i, mut j) = (0, b.len() - 1);
while i < j && a[i] == b[j] {
i += 1;
j -= 1;
}
if i >= j {
return true;
}
check2(a, i, j) || check2(b, i, j)
}
fn check2(a: &[u8], mut i: usize, mut j: usize) -> bool {
while i < j && a[i] == a[j] {
i += 1;
j -= 1;
}
i >= j
}
let a = a.as_bytes();
let b = b.as_bytes();
check1(a, b) || check1(b, a)
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Two Pointer Technique | Time Complexity: O(n), where n is the length of strings, achieved by continual pointer adjustments. |
| Recursive Backtracking | Time Complexity: O(n), rapid cut through segments on recursion. |
| Two Pointers | – |
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 |
Frequently asked questions
Is Split Two Strings to Make Palindrome easy or hard?
The problem is rated Medium because the implementation is simple once the insight is known. The challenge is recognizing that only the mismatch region needs a palindrome check instead of testing every possible split.
How to solve Split Two Strings to Make Palindrome in O(n)?
Use two pointers to compare a prefix of one string with the suffix of the other. Move inward while characters match. Once a mismatch appears, verify whether the remaining substring in either string forms a palindrome using a simple two-pointer check. If either substring is a palindrome, the split works.
Split Two Strings to Make Palindrome Python or Java solution
In Python or Java, implement a helper function that checks if a substring is a palindrome using two pointers. Then compare the prefix of one string with the suffix of the other until a mismatch appears. Validate the remaining substring using the helper function to determine if a valid split exists.
What is the best approach for Split Two Strings to Make Palindrome?
The two pointer technique is the best approach. Start comparing characters from the beginning of one string and the end of the other. When a mismatch occurs, check if the remaining substring in either string is already a palindrome. This reduces the problem to O(n) time and O(1) extra space.
Is Split Two Strings to Make Palindrome asked at Google/Amazon/Meta?
Palindrome and two-pointer string problems appear frequently in interviews at companies like Google, Amazon, and Meta. Variants of this question test your ability to recognize symmetry and reduce brute-force string comparisons to linear scans.
What data structure is used in Split Two Strings to Make Palindrome?
The problem mainly uses string traversal with the two pointer technique. No additional data structures such as hash maps or stacks are required. Only index pointers are maintained while comparing characters from both ends.
What is the time complexity of Split Two Strings to Make Palindrome?
The optimal solution runs in O(n) time where n is the string length. Two pointers scan the strings once, and at most one additional palindrome check is performed on a substring. Space complexity remains O(1) because only indices are tracked.