Skip to content

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