# Split Two Strings to Make Palindrome
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/split-two-strings-to-make-palindrome)
Canonical: https://scaleengineer.com/dsa/problems/split-two-strings-to-make-palindrome
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers)
**Data structures:** String
---
## 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 <= 105`
* `a.length == b.length`
* `a` and `b` consist of lowercase English letters

# Approaches
## Brute Force Iteration
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.
**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.
**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.
### Explanation
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`.

```java
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;
    }
}
```
### Algorithm
- Iterate through every possible split index `i` from `0` to `n`, where `n` is 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)`, and `b_suffix = b.substring(i)`.
  - Form two new strings: `s1 = a_prefix + b_suffix` and `s2 = b_prefix + a_suffix`.
  - Check if `s1` is a palindrome using a helper function.
  - If `s1` is a palindrome, return `true` immediately.
  - Check if `s2` is a palindrome.
  - If `s2` is a palindrome, return `true` immediately.
- If the loop completes without finding any palindrome, return `false`.

## Greedy Two-Pointer Approach
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.
**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.
**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.
### Explanation
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.

```java
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;
    }
}
```
### Algorithm
- The main function `checkPalindromeFormation` checks two symmetric cases: `check(a, b)` and `check(b, a)`. If either returns `true`, the result is `true`.
- The helper function `check(s1, s2)` determines if `s1_prefix + s2_suffix` can form a palindrome.
- Inside `check(s1, s2)`:
  - Use two pointers, `left` starting at `0` and `right` at `n-1`.
  - Greedily match the outer characters: while `left < right` and `s1.charAt(left) == s2.charAt(right)`, increment `left` and decrement `right`.
  - This loop finds the longest prefix of `s1` that matches the reverse of a suffix of `s2`.
  - After the loop, the outer parts of a potential palindrome are confirmed. The remaining middle part, from index `left` to `right`, must also be a palindrome.
  - This middle part can be formed either by the substring from `s1` (`s1[left...right]`) or the substring from `s2` (`s2[left...right]`).
  - Check if `isPalindrome(s1, left, right)` or `isPalindrome(s2, left, right)` is true. Return the result of this logical OR.
- The `isPalindrome(s, left, right)` helper function checks if a substring is a palindrome in O(N) time without creating a new string.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
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;
  }
};

```

### Python

```python
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)

```