Example 3:

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

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

Code

[{"language":"C++","code":"class Solution {\npublic:\n    bool check(const string& a, const string& b) {\n        int l = 0, r = a.size() - 1;\n        while (l < r && a[l] == b[r]) {\n            ++l; --r;\n        }\n        return isPalindrome(a, l, r) || isPalindrome(b, l, r);\n    }\n    bool isPalindrome(const string& s, int l, int r) {\n        while (l < r) if (s[l++] != s[r--]) return false;\n        return true;\n    }\n    bool checkPalindromeFormation(string a, string b) {\n        return check(a, b) || check(b, a);\n    }\n};","lang":"cpp"},{"language":"Go","code":"func isPalindrome(s string, l, r int) bool {\n    for l < r {\n        if s[l] != s[r] {\n            return false\n        }\n        l++\n        r--\n    }\n    return true\n}\nfunc check(a, b string) bool {\n    l, r := 0, len(a)-1\n    for l < r && a[l] == b[r] {\n        l++\n        r--\n    }\n    return isPalindrome(a, l, r) || isPalindrome(b, l, r)\n}\nfunc checkPalindromeFormation(a, b string) bool {\n    return check(a, b) || check(b, a)\n}","lang":"go"},{"language":"Java","code":"class Solution {\n    private boolean isPalindrome(String s, int l, int r) {\n        while (l < r) if (s.charAt(l++) != s.charAt(r--)) return false;\n        return true;\n    }\n    private boolean check(String a, String b) {\n        int l = 0, r = a.length() - 1;\n        while (l < r && a.charAt(l) == b.charAt(r)) {\n            l++;\n            r--;\n        }\n        return isPalindrome(a, l, r) || isPalindrome(b, l, r);\n    }\n    public boolean checkPalindromeFormation(String a, String b) {\n        return check(a, b) || check(b, a);\n    }\n}","lang":"java"},{"language":"Kotlin","code":"class Solution {\n    fun checkPalindromeFormation(a: String, b: String): Boolean {\n        fun isPalindrome(s: String, l: Int, r: Int): Boolean {\n            var i = l\n            var j = r\n            while (i < j) {\n                if (s[i] != s[j]) return false\n                i++\n                j--\n            }\n            return true\n        }\n        fun check(a: String, b: String): Boolean {\n            var l = 0\n            var r = a.length - 1\n            while (l < r && a[l] == b[r]) {\n                l++\n                r--\n            }\n            return isPalindrome(a, l, r) || isPalindrome(b, l, r)\n        }\n        return check(a, b) || check(b, a)\n    }\n}","lang":"kotlin"},{"language":"Python","code":"class Solution:\n    def checkPalindromeFormation(self, a: str, b: str) -> bool:\n        def is_pal(s: str, l: int, r: int) -> bool:\n            while l < r:\n                if s[l] != s[r]:\n                    return False\n                l += 1\n                r -= 1\n            return True\n        def check(a: str, b: str) -> bool:\n            l, r = 0, len(a) - 1\n            while l < r and a[l] == b[r]:\n                l += 1\n                r -= 1\n            return is_pal(a, l, r)

Related Tags