1616. Split Two Strings to Make Palindrome

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.

class Solution {
    bool isPalindrome(string &s, int odd) {
        if((!(s.length() & 1) && odd != 0) || ((s.length() & 1) && odd != 1))
            return false;

        int start = 0, end = s.length() - 1;
        while(start < end) {
            if(s[start] != s[end]) return false;
            start++, end--;
        }
        return true;
    }
public:
    bool checkPalindromeFormation(string a, string b) {
        unordered_map<char, int> aMap, bMap;
        int len = a.length(), aOdd = 0, bOdd = 0;
        for(int i = 0; i < len; i++) {
            aMap[a[i]]++;
            bMap[b[i]]++;
        }
        for(auto entity : aMap) {
            if(entity.second & 1) aOdd++;
        }

        for(auto entity : bMap) {
            if(entity.second & 1) bOdd++;
        }

        if(isPalindrome(a, aOdd) || isPalindrome(b, bOdd)) return true;
        for(int i = 0; i < len; i++) {
            aOdd += aMap[a[i]] & 1 ? 1 : -1;
            aOdd += aMap[b[i]] & 1 ? 1 : -1;
            bOdd += bMap[a[i]] & 1 ? 1 : -1;
            bOdd += bMap[b[i]] & 1 ? 1 : -1;
            aMap[a[i]]--;
            bMap[b[i]]--;
            aMap[b[i]]++;
            bMap[a[i]]++;
            swap(a[i], b[i]);
            if(isPalindrome(a, aOdd) || isPalindrome(b, bOdd)) return true;
        }

        return false;
    }
};