Split Two Strings to Make Palindrome - Practice Coding Problems

Split Two Strings to Make Palindrome - Problem

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.

Input & Output

Example 1 — Basic Valid Case

$ Input: a = "x", b = "y"

› Output: true

💡 Note: Split at position 0: aprefix="" + bsuffix="y" = "y" (palindrome), or split at position 1: aprefix="x" + bsuffix="" = "x" (palindrome)

Example 2 — Valid Combination

$ Input: a = "xbdef", b = "xecab"

› Output: false

💡 Note: No split position creates a palindrome: splitting anywhere produces non-palindromic combinations

Example 3 — Another Valid Case

$ Input: a = "ulacfd", b = "jizalu"

› Output: true

💡 Note: Split at position 3: aprefix="ula" + bsuffix="alu" = "ulaalu" (palindrome)

Constraints

1 ≤ a.length, b.length ≤ 10⁵
a.length == b.length
a and b consist of lowercase English letters

Visualization

Tap to expand

Understanding the Visualization

Input

Two strings a and b of equal length

Process

Find split position where aprefix+bsuffix or bprefix+asuffix forms palindrome

Output

Return true if palindrome possible, false otherwise

Key Takeaway

🎯 Key Insight: Use two pointers to efficiently check if strings can be split to form palindromes by comparing from both ends

Asked in

F Facebook 25 G Google 20

The key insight is to use two pointers from both ends to efficiently find where strings can be split to form palindromes. Best approach uses two pointers optimization with O(n) time and O(1) space complexity.

Common Approaches

Approach	Time	Space	Notes
✓ Two Pointers Optimization	O(n)	O(1)	Use two pointers from both ends to efficiently find valid split points
Brute Force	O(n²)	O(n)	Try all possible split positions and check if combinations form palindromes

Two Pointers Optimization — Algorithm Steps

Step 1: Use two pointers from start and end of both strings
Step 2: Move pointers inward while characters match
Step 3: When mismatch found, check if remaining parts can form palindromes

Visualization

Tap to expand

Step-by-Step Walkthrough

Start from ends

Place pointers at start and end of strings

Move inward while matching

Advance pointers when characters match

Check remaining on mismatch

When mismatch found, check if remaining parts form palindromes

Code -

solution.c — C

#include <stdio.h>
#include <string.h>
#include <stdbool.h>

bool isPalindromeRange(char* s, int left, int right) {
    while (left < right) {
        if (s[left] != s[right]) {
            return false;
        }
        left++;
        right--;
    }
    return true;
}

bool checkPalindrome(char* s1, char* s2) {
    int left = 0, right = strlen(s1) - 1;
    while (left < right) {
        if (s1[left] == s2[right]) {
            left++;
            right--;
        } else {
            return isPalindromeRange(s1, left, right) || 
                   isPalindromeRange(s2, left, right);
        }
    }
    return true;
}

bool solution(char* a, char* b) {
    return checkPalindrome(a, b) || checkPalindrome(b, a);
}

int main() {
    char a[501], b[501];
    fgets(a, sizeof(a), stdin);
    fgets(b, sizeof(b), stdin);
    a[strcspn(a, "\n")] = 0;
    b[strcspn(b, "\n")] = 0;
    bool result = solution(a, b);
    printf(result ? "true\n" : "false\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Two pointers traverse string once, palindrome checks are done on smaller substrings

✓ Linear Growth

Space Complexity

O(1)

Only using constant extra space for pointers and variables

✓ Linear Space

28.5K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Two Pointers Optimization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler