Leetcode: Longest Chunked Palindrome Decomposition

Posted on August 5, 2019October 30, 2019 by braindenny

Longest Chunked Palindrome Decomposition

Similar Problems:

Return the largest possible k such that there exists a_1, a_2, …, a_k such that:

Each a_i is a non-empty string;
Their concatenation a_1 + a_2 + … + a_k is equal to text;
For all 1 <= i <= k, a_i = a_{k+1 – i}.

Example 1:

Input: text = "ghiabcdefhelloadamhelloabcdefghi"
Output: 7
Explanation: We can split the string on "(ghi)(abcdef)(hello)(adam)(hello)(abcdef)(ghi)".

Example 2:

Input: text = "merchant"
Output: 1
Explanation: We can split the string on "(merchant)".

Example 3:

Input: text = "antaprezatepzapreanta"
Output: 11
Explanation: We can split the string on "(a)(nt)(a)(pre)(za)(tpe)(za)(pre)(a)(nt)(a)".

Example 4:

Input: text = "aaa"
Output: 3
Explanation: We can split the string on "(a)(a)(a)".

Constraints:

text consists only of lowercase English characters.
1 <= text.length <= 1000

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

Solution: Rabin Karp Algorithm – rollinghash

// https://code.dennyzhang.com/longest-chunked-palindrome-decomposition
// Basic Ideas: Rabin Karp Algorithm - rollinghash
//
// Complexity: Time O(n*n), Space O(n)
import "math"
func longestDecomposition(text string) int {
    res := 0
    mod := int(math.Pow(10, 9)+5)
    pow := 1
    left, right := 0, 0
    // two direction moves in the same speed
    for i:=0; i<len(text); i++ {
        j := len(text)-1-i
        left = (left*26 + int(text[i]-'a')) % mod
        right = (int(text[j]-'a')*pow + right) % mod
        pow = (pow*26)%mod
        // after i, j meets, we count it one more time
        if left == right {
            res += 1
            left, right = 0, 0
            pow = 1
        }
    }
    return res
}

Solution: twopointer + move to the ends

// https://code.dennyzhang.com/longest-chunked-palindrome-decomposition
// Basic Ideas: twopointer
//
// Complexity: Time O(n*n), Space O(1)
func longestDecomposition(text string) int {
    res := 0
    left, right := "", ""
    // two direction moves in the same speed
    for i:=0; i<len(text); i++ {
        j := len(text)-1-i
        left = left + string(text[i])
        right = string(text[j]) + right
        // after i, j meets, we count it one more time
        if left == right {
            res += 1
            left, right = "", ""
        }
    }
    return res
}

Solution: twopointer + move to half

// https://code.dennyzhang.com/longest-chunked-palindrome-decomposition
// Basic Ideas: twopointer
//
// Complexity: Time O(n*n), Space O(1)
func longestDecomposition(text string) int {
    res := 0
    left, right := "", ""
    // check the half
    for i:=0; i<len(text)/2; i++ {
        j := len(text)-1-i
        left = left + string(text[i])
        right = string(text[j]) + right
        if left == right {
            res += 2
            left, right = "", ""
        }
    }

    if len(text)%2 == 1 && left == "" {
        // middle element
        res++
    } else {
        // not matched
        if left != "" {
         res++
       } 
    }
    return res
}

Post Views: 0