# 1616. Split Two Strings to Make Palindrome

• Time: $O(n)$
• Space: $O(1)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 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; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 public 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; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 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