1616. Split Two Strings to Make Palindrome LeetCode Solution

In this guide, you will get 1616. Split Two Strings to Make Palindrome LeetCode Solution with the best time and space complexity. The solution to Split Two Strings to Make Palindrome problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

1. Problem Statement
2. Complexity Analysis
3. Split Two Strings to Make Palindrome solution in C++
4. Split Two Strings to Make Palindrome solution in Java
5. Split Two Strings to Make Palindrome solution in Python
6. Additional Resources

Problem Statement of Split Two Strings to Make Palindrome

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

Complexity Analysis

• Time Complexity: O(n)
• Space Complexity: O(1)

1616. Split Two Strings to Make Palindrome LeetCode Solution in C++

class Solution {
 public:
  bool checkPalindromeFormation(string a, string b) {
    return check(a, b) || check(b, a);
  }

 private:
  bool check(const string& a, const string& b) {
    for (int i = 0, j = a.length() - 1; i < j; ++i, --j)
      if (a[i] != b[j])
        // a[0:i] + a[i..j] + b[j + 1:] or
        // a[0:i] + b[i..j] + b[j + 1:]
        return isPalindrome(a, i, j) || isPalindrome(b, i, j);
    return true;
  }

  bool isPalindrome(const string& s, int i, int j) {
    while (i < j)
      if (s[i++] != s[j--])
        return false;
    return true;
  }
};
/* code provided by PROGIEZ */

1616. Split Two Strings to Make Palindrome LeetCode Solution in Java

class Solution {
  public boolean checkPalindromeFormation(String a, String b) {
    return check(a, b) || check(b, a);
  }

  private boolean check(String a, String b) {
    for (int i = 0, j = a.length() - 1; i < j; ++i, --j)
      if (a.charAt(i) != b.charAt(j))
        // a[0:i] + a[i..j] + b[j + 1:] or
        // a[0:i] + b[i..j] + b[j + 1:]
        return isPalindrome(a, i, j) || isPalindrome(b, i, j);
    return true;
  }

  private boolean isPalindrome(String s, int i, int j) {
    while (i < j)
      if (s.charAt(i++) != s.charAt(j--))
        return false;
    return true;
  }
}
// code provided by PROGIEZ

1616. Split Two Strings to Make Palindrome LeetCode Solution in Python

class Solution:
  def checkPalindromeFormation(self, a: str, b: str) -> bool:
    return self._check(a, b) or self._check(b, a)

  def _check(self, a: str, b: str) -> bool:
    i, j = 0, len(a) - 1
    while i < j:
      if a[i] != b[j]:
        # a[0:i] + a[i..j] + b[j + 1:] or
        # a[0:i] + b[i..j] + b[j + 1:]
        return self._isPalindrome(a, i, j) or self._isPalindrome(b, i, j)
      i += 1
      j -= 1
    return True

  def _isPalindrome(self, s: str, i: int, j: int) -> bool:
    while i < j:
      if s[i] != s[j]:
        return False
      i += 1
      j -= 1
    return True
 # code by PROGIEZ

Additional Resources

• Explore all LeetCode problem solutions at Progiez here
• Explore all problems on LeetCode website here

Happy Coding! Keep following PROGIEZ for more updates and solutions.