We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Split Two Strings to Make Palindrome

Number: 1739

Difficulty: Medium

Paid? No

Companies: Google

Problem Description

Given two strings a and b of the same length, determine if there exists an index at which both strings can be split (with one part possibly empty) so that either a_prefix + b_suffix or b_prefix + a_suffix forms a palindrome.

Key Insights

  • A palindrome reads the same forward and backward.
  • The index of splitting is the same for both strings.
  • Check both possible concatenations: a_prefix + b_suffix and b_prefix + a_suffix.
  • Use a two-pointer strategy to match characters from two ends until a mismatch occurs.
  • After the initial matching, verify if the remaining substring in one of the strings is a palindrome.

Space and Time Complexity

Time Complexity: O(n) – In the worst case, we traverse the strings with two pointers. Space Complexity: O(1) – Only constant extra space is used.

Solution

The solution uses a two-pointer approach to check for palindrome formation. For a given concatenation (e.g., a_prefix + b_suffix), we start with two pointers: one at the beginning of string a and one at the end of string b. We move the pointers inward as long as the characters match.

If a mismatch occurs, there are two possibilities to check:

  1. The remaining substring in a (from the current left pointer to the current right pointer) is a palindrome.
  2. The remaining substring in b (from the current left pointer to the current right pointer) is a palindrome.

We perform this check for both possible orders (a_prefix + b_suffix and b_prefix + a_suffix). If either returns true, then it is possible to form a palindrome through a proper split.

Data Structures and Algorithmic Approach:

  • Two pointers for iterating over the strings.
  • A helper method to check if a substring is a palindrome.
  • The greedy matching strategy minimizes the number of characters to check.

Code Solutions

# Python solution with line-by-line comments.
class Solution:
    def checkPalindromeFormation(self, a: str, b: str) -> bool:
        # Helper function to check if s[l:r+1] is a palindrome.
        def isPalindrome(s, l, r):
            while l < r:
                if s[l] != s[r]:
                    return False
                l += 1
                r -= 1
            return True

        # Function that checks whether a_prefix + b_suffix can form a palindrome.
        def check(x, y):
            l, r = 0, len(x) - 1
            # Move inward while the characters match
            while l < r and x[l] == y[r]:
                l += 1
                r -= 1
            # Check if the remaining substring in x or y is a palindrome.
            return isPalindrome(x, l, r) or isPalindrome(y, l, r)

        # Check both order combinations.
        return check(a, b) or check(b, a)
← Back to All Questions