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.

Notice that x + y denotes the concatenation of strings x and y.

Examples

Example 1:

1
2
3
4
5
6
7
8

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:

1
2
3
4

Input:
a = "xbdef", b = "xecab"
Output:
 false

Example 3:

1
2
3
4
5
6
7
8

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.

Solution

Method 1 – Two Pointers Greedy

Intuition

To form a palindrome by splitting at some index, we can try to match the prefix of one string with the suffix of the other. If a mismatch occurs, check if the remaining substring in either string is a palindrome. If so, the answer is true.

Approach

  1. Define a helper to check if a substring is a palindrome.
  2. For both (a, b) and (b, a), use two pointers (l, r) to compare a[l] with b[r].
  3. If a mismatch occurs, check if the remaining substring in either string is a palindrome.
  4. If any combination returns true, return true; otherwise, return false.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
public:
    bool check(const string& a, const string& b) {
        int l = 0, r = a.size() - 1;
        while (l < r && a[l] == b[r]) {
            ++l; --r;
        }
        return isPalindrome(a, l, r) || isPalindrome(b, l, r);
    }
    bool isPalindrome(const string& s, int l, int r) {
        while (l < r) if (s[l++] != s[r--]) return false;
        return true;
    }
    bool checkPalindromeFormation(string a, string b) {
        return check(a, b) || check(b, a);
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

func isPalindrome(s string, l, r int) bool {
    for l < r {
        if s[l] != s[r] {
            return false
        }
        l++
        r--
    }
    return true
}
func check(a, b string) bool {
    l, r := 0, len(a)-1
    for l < r && a[l] == b[r] {
        l++
        r--
    }
    return isPalindrome(a, l, r) || isPalindrome(b, l, r)
}
func checkPalindromeFormation(a, b string) bool {
    return check(a, b) || check(b, a)
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    private boolean isPalindrome(String s, int l, int r) {
        while (l < r) if (s.charAt(l++) != s.charAt(r--)) return false;
        return true;
    }
    private boolean check(String a, String b) {
        int l = 0, r = a.length() - 1;
        while (l < r && a.charAt(l) == b.charAt(r)) {
            l++;
            r--;
        }
        return isPalindrome(a, l, r) || isPalindrome(b, l, r);
    }
    public boolean checkPalindromeFormation(String a, String b) {
        return check(a, b) || check(b, a);
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
    fun checkPalindromeFormation(a: String, b: String): Boolean {
        fun isPalindrome(s: String, l: Int, r: Int): Boolean {
            var i = l
            var j = r
            while (i < j) {
                if (s[i] != s[j]) return false
                i++
                j--
            }
            return true
        }
        fun check(a: String, b: String): Boolean {
            var l = 0
            var r = a.length - 1
            while (l < r && a[l] == b[r]) {
                l++
                r--
            }
            return isPalindrome(a, l, r) || isPalindrome(b, l, r)
        }
        return check(a, b) || check(b, a)
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution:
    def checkPalindromeFormation(self, a: str, b: str) -> bool:
        def is_pal(s: str, l: int, r: int) -> bool:
            while l < r:
                if s[l] != s[r]:
                    return False
                l += 1
                r -= 1
            return True
        def check(a: str, b: str) -> bool:
            l, r = 0, len(a) - 1
            while l < r and a[l] == b[r]:
                l += 1
                r -= 1
            return is_pal(a, l, r) or is_pal(b, l, r)
        return check(a, b) or check(b, a)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

impl Solution {
    pub fn check_palindrome_formation(a: String, b: String) -> bool {
        fn is_pal(s: &str, l: usize, r: usize) -> bool {
            let s = s.as_bytes();
            let mut i = l;
            let mut j = r;
            while i < j {
                if s[i] != s[j] { return false; }
                i += 1;
                j -= 1;
            }
            true
        }
        fn check(a: &str, b: &str) -> bool {
            let (mut l, mut r) = (0, a.len() - 1);
            let a = a.as_bytes();
            let b = b.as_bytes();
            while l < r && a[l] == b[r] {
                l += 1;
                r -= 1;
            }
            is_pal(std::str::from_utf8(a).unwrap(), l, r) || is_pal(std::str::from_utf8(b).unwrap(), l, r)
        }
        check(&a, &b) || check(&b, &a)
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
    checkPalindromeFormation(a: string, b: string): boolean {
        function isPal(s: string, l: number, r: number): boolean {
            while (l < r) {
                if (s[l] !== s[r]) return false;
                l++;
                r--;
            }
            return true;
        }
        function check(a: string, b: string): boolean {
            let l = 0, r = a.length - 1;
            while (l < r && a[l] === b[r]) {
                l++;
                r--;
            }
            return isPal(a, l, r) || isPal(b, l, r);
        }
        return check(a, b) || check(b, a);
    }
}

Complexity

  • ⏰ Time complexity: O(n), where n is the length of the strings. Each check is linear.
  • 🧺 Space complexity: O(1), only constant extra space is used.