給你兩個字符串 a 和 b ，它們長度相同。請你選擇一個下標，將兩個字符串都在 相同的下標 分割開。由 a 可以得到兩個字符串： aprefix 和 asuffix ，滿足 a = aprefix + asuffix ，同理，由 b 可以得到兩個字符串 bprefix 和 bsuffix ，滿足 b = bprefix + bsuffix 。請你判斷 aprefix + bsuffix 或者 bprefix + asuffix 能否構成回文串。

當你將一個字符串 s 分割成 sprefix 和 ssuffix 時， ssuffix 或者 sprefix 可以為空。比方說， s = “abc” 那么 “” + “abc” ， “a” + “bc” ， “ab” + “c” 和 “abc” + “” 都是合法分割。

如果 能構成回文字符串 ，那么請返回 true，否則返回 false 。

注意， x + y 表示連接字符串 x 和 y 。

示例 1：

輸入：a = “x”, b = “y”
輸出：true
解釋：如果 a 或者 b 是回文串，那么答案一定為 true ，因為你可以如下分割：
aprefix = “”, asuffix = “x”
bprefix = “”, bsuffix = “y”
那么 aprefix + bsuffix = “” + “y” = “y” 是回文串。
示例 2：

輸入：a = “xbdef”, b = “xecab”
輸出：false
示例 3：

輸入：a = “ulacfd”, b = “jizalu”
輸出：true
解釋：在下標為 3 處分割：
aprefix = “ula”, asuffix = “cfd”
bprefix = “jiz”, bsuffix = “alu”
那么 aprefix + bsuffix = “ula” + “alu” = “ulaalu” 是回文串。

提示：

1 <= a.length, b.length <= 10${}^5$
a.length == b.length
a 和 b 都只包含小寫英文字母

我們可以先對比a的開頭和b的結尾，直到找到第一個不相同的字符，如下圖：

接下來我們只需檢查第一行中間部分和第二行中間部分是否是回文的即可，只要任意一個是回文串，那么就可以分割得到回文串：

class Solution {
public:bool checkPalindromeFormation(string a, string b) {return check(a, b) || check(b, a);}bool check(string &a, string &b) {int left = 0;int right = a.size() - 1;// 找到第一個不相等的字符while (left < right) {if (a[left] != b[right]) {break;}++left;--right;}bool bGood = true;bool aGood = true;while (left < right) {if (b[left] != b[right]) {bGood = false;}if (a[left] != a[right]) {aGood = false;}// 如果兩個串的中間部分都不是回文串if (!aGood && !bGood) {return false;}++left;--right;}return true;}
};

如果字符串的長度為n，則此算法時間復雜度為O(n)，空間復雜度為O(1)。