Scale Engineer

Split Two Strings to Make Palindrome

Med
#1485Time: 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.
Patterns
Two Pointers
Data structures
String

Prompt

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

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 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.

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.

Solutions

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

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.

← Previous

Previous problem

Next →

Next problem