Split Two Strings to Make Palindrome

Medium

Asked by:

14 views

Topics:

StringsTwo Pointers

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

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the input strings `a` and `b` be empty or null? What should I return in such cases?
What are the maximum lengths of strings `a` and `b`?
Are the strings `a` and `b` guaranteed to have the same length?
By 'split', do you mean that I can only use a prefix of one string and a suffix of the other to form a palindrome, and these prefix and suffix must be contiguous?
If there are multiple valid splits that result in a palindrome, do I need to return all of them, or is returning 'true' sufficient?

Brute Force Solution

Approach

The brute force approach to this problem involves checking every possible way to split the two strings. We are essentially trying every combination of prefixes from one string and suffixes from the other to see if they form a palindrome, or vice versa.

Here's how the algorithm would work step-by-step:

Take the first string and consider all the ways you could split it into two parts: a beginning section and an ending section.
For each of these splits, take the ending section of the first string and combine it with the beginning section of the second string.
Check if this combined string is a palindrome (reads the same forwards and backward).
Repeat the same process but swap the roles of the two strings. That is, take all possible ending sections from the second string and combine them with the beginning sections of the first string.
Again, check if these combined strings are palindromes.
If you find any combination that creates a palindrome, then you have found a solution.

Code Implementation

def can_form_palindrome(first_string, second_string):
    string_length = len(first_string)

    def is_palindrome(input_string):
        return input_string == input_string[::-1]

    # Iterate through possible split points in the first string
    for split_index in range(string_length):
        first_string_prefix = first_string[:split_index]
        first_string_suffix = first_string[split_index:]

        # Check if suffix of first string and prefix of second string form a palindrome
        combined_string_one = first_string_suffix + second_string[:string_length - split_index]
        if is_palindrome(combined_string_one):
            return True

        # Check if suffix of second string and prefix of first string form a palindrome
        second_string_prefix = second_string[:split_index]
        second_string_suffix = second_string[split_index:]

        combined_string_two = second_string_suffix + first_string[:string_length - split_index]
        if is_palindrome(combined_string_two):
            return True

    return False

def split_two_strings(first_string, second_string):
    # Check if either combination of splits can form a palindrome
    if can_form_palindrome(first_string, second_string):
        return True
    # Need to also check the other string order too

    if can_form_palindrome(second_string, first_string):
        return True

    # If no combination created a palindrone, return false
    return False

Big(O) Analysis

Time Complexity

O(n²) – The described algorithm iterates through all possible split points of the two strings, each of length n. For each split, it constructs a combined string, which takes O(n) time. It then checks if this combined string is a palindrome, which also takes O(n) time. Since there are n possible splits and for each split we perform O(n) operations to construct and check for a palindrome, the overall time complexity is O(n * n), or O(n²). This holds true regardless of which string's prefix or suffix is being combined.

Space Complexity

O(1) – The provided algorithm primarily performs string slicing and concatenation to check for palindromes. While string slicing might create new string objects in some implementations, and string concatenation surely does, these temporary strings do not depend on the input size; they are implicitly managed and deallocated within the loop's iterations. There are no explicitly created auxiliary data structures like arrays, hashmaps, or recursion involved, hence the space used beyond the input strings is constant. The space used for variables like loop counters and boolean flags does not scale with the input size, N, either. Therefore, the auxiliary space complexity is O(1).

Optimal Solution

Approach

The challenge is to combine two strings to create a palindrome. Instead of exhaustively checking all combinations, we cleverly look for a 'split point' where we can combine parts of the two strings to form a palindrome efficiently.

Here's how the algorithm would work step-by-step:

Imagine cutting each string into two pieces at various points.
For each cut, try to glue the first part of the first string with the second part of the second string.
Check if this combined string is a palindrome. If it is, you're done!
If that doesn't work, try the reverse: glue the first part of the second string with the second part of the first string.
Again, check if this combined string is a palindrome. If it is, you're done!
To efficiently check if a part of a string can form a palindrome with the other part, we examine the beginning and ending characters moving toward the middle.
If at any point the characters don't match, the substrings can't form a palindrome, so move on to the next possible cut.
If you find a cut that makes a palindrome, the answer is 'yes'. Otherwise, if you've tried all the cuts, the answer is 'no'.

Code Implementation

def split_strings_to_make_palindrome(string_a, string_b):
    string_length = len(string_a)

    def is_palindrome(input_string):
        left_index = 0
        right_index = len(input_string) - 1
        while left_index < right_index:
            if input_string[left_index] != input_string[right_index]:
                return False
            left_index += 1
            right_index -= 1
        return True

    def check_strings(first_string, second_string):
        left_index = 0
        right_index = string_length - 1

        # Find the longest prefix of first_string that matches the suffix of second_string.
        while left_index < right_index and first_string[left_index] == second_string[right_index]:
            left_index += 1
            right_index -= 1

        # Check if the remaining part of either string is a palindrome.
        if left_index >= right_index:
            return True
        sub_string = first_string[left_index:right_index + 1]

        return is_palindrome(sub_string)

    # Check if either combination results in a palindrome.
    if check_strings(string_a, string_b) or check_strings(string_b, string_a):
        return True

    return False

Big(O) Analysis

Time Complexity

O(n) – The primary operation involves iterating through potential split points in the two input strings, each of length n. For each split point, a helper function 'checkPalindrome' is used, but this helper function's execution time is at most O(n) as it iterates from both ends to the middle of a substring. However, the key optimization is that 'checkPalindrome' only runs on the differing portions of the string after the initial common prefix is identified. Therefore, although nested in structure, the complexity will be O(n), because, in total, characters are iterated over a limited amount of times.

Space Complexity

O(1) – The algorithm primarily uses a few integer variables to track the split point and indices during palindrome checks. No auxiliary data structures like lists or hash maps are created. The space required remains constant regardless of the lengths of the input strings, so the auxiliary space complexity is O(1).

Edge Cases

Case	How to Handle
Both strings are empty	Return true, as an empty string is considered a palindrome.
One string is empty, the other is not.	Treat the non-empty string as the result of the merge and check if it is a palindrome.
Strings of length 1.	Check if either string is a palindrome by itself (single character is always a palindrome).
Strings are palindromes themselves.	Return True, as no splitting or merging is necessary.
Strings of very large length (performance)	Ensure algorithm avoids unnecessary string copying or repeated palindrome checks for optimal time complexity.
No split point results in a palindrome (e.g., 'abc', 'def')	Return false if all split and merge combinations fail to produce a palindrome.
Strings are identical but non-palindromic.	Any split point will result in a merge that isn't a palindrome, so return false.
Palindrome can be formed only when string a is prefix.	The algorithm should check for both scenarios: a prefix + b suffix and b prefix + a suffix.

Both strings are empty

How to Handle:

Return true, as an empty string is considered a palindrome.

One string is empty, the other is not.

How to Handle:

Treat the non-empty string as the result of the merge and check if it is a palindrome.

Strings of length 1.

How to Handle:

Check if either string is a palindrome by itself (single character is always a palindrome).

Strings are palindromes themselves.

How to Handle:

Return True, as no splitting or merging is necessary.

Strings of very large length (performance)

How to Handle:

Ensure algorithm avoids unnecessary string copying or repeated palindrome checks for optimal time complexity.

No split point results in a palindrome (e.g., 'abc', 'def')

How to Handle:

Return false if all split and merge combinations fail to produce a palindrome.

Strings are identical but non-palindromic.

How to Handle:

Any split point will result in a merge that isn't a palindrome, so return false.

Palindrome can be formed only when string a is prefix.

How to Handle:

The algorithm should check for both scenarios: a prefix + b suffix and b prefix + a suffix.