Split Two Strings to Make Palindrome

MEDIUM

Description

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: a_prefix and a_suffix where a = a_prefix + a_suffix, and splitting b into two strings: b_prefix and b_suffix where b = b_prefix + b_suffix. Check if a_prefix + b_suffix or b_prefix + a_suffix forms a palindrome.

When you split a string s into s_prefix and s_suffix, either s_suffix or s_prefix 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:
a_prefix = "", a_suffix = "x"
b_prefix = "", b_suffix = "y"
Then, a_prefix + b_suffix = "" + "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:
a_prefix = "ula", a_suffix = "cfd"
b_prefix = "jiz", b_suffix = "alu"
Then, a_prefix + b_suffix = "ula" + "alu" = "ulaalu", which is a palindrome.

Constraints:

1 <= a.length, b.length <= 10⁵
a.length == b.length
a and b consist of lowercase English letters

Approaches

Checkout 2 different approaches to solve Split Two Strings to Make Palindrome. Click on different approaches to view the approach and algorithm in detail.

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.

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.

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 Analysis

Time Complexity: 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 Complexity: 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 and Cons

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.

Code Solutions

Checking out 3 solutions in different languages for Split Two Strings to Make Palindrome. Click on different languages to view the code.

Video Solution

Watch the video walkthrough for Split Two Strings to Make Palindrome

Patterns:

Two Pointers

Data Structures:

String