段式回文

1147. 段式回文

你会得到一个字符串 text 。你应该把它分成 k 个子字符串 (subtext1, subtext2，…， subtextk) ，要求满足:

• subtexti 是 非空 字符串
• 所有子字符串的连接等于 text ( 即subtext1 + subtext2 + ... + subtextk == text )
• 对于所有 i 的有效值( 即 1 <= i <= k ) ，subtexti == subtextk - i + 1 均成立

返回k可能最大值。

示例 1：

输入：text = "ghiabcdefhelloadamhelloabcdefghi"
输出：7
解释：我们可以把字符串拆分成 "(ghi)(abcdef)(hello)(adam)(hello)(abcdef)(ghi)"。

示例 2：

输入：text = "merchant"
输出：1
解释：我们可以把字符串拆分成 "(merchant)"。

题解：双指针+贪心

/**
 * @param {string} text
 * @return {number}
 */
var longestDecomposition = function(text) {
    let n = text.length;
    let i = 0, j = n - 1, ans = 0;
    let s1 = '', s2 = '';
    while(1) {
        if (i >= j){
            break;
        }
        s1 += text[i];
        s2 = text[j] + s2;
        if (s1 === s2) {
            ans++;
            s1 = '';
            s2 = '';
            if (i + 1 === j) {
                return 2 * ans;
            }
        }
        i++;
        j--;
    }
    // 如果无法找到重复子序列，直接返回最小分解数乘以2再加1，表示字符串不能再分解了
    return ans * 2 + 1;
};