LeetCode: Longest Chunked Palindrome Decomposition Posted on August 5, 2019July 26, 2020 by braindenny Longest Chunked Palindrome Decomposition Similar Problems: CheatSheet: Leetcode For Code Interview CheatSheet: Common Code Problems & Follow-ups Tag: #palindrome, #twopointer, #rollinghash 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(1) import "math" func longestDecomposition(text string) int { mod := int(math.Pow(10, 9)+5) res := 0 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 Post navigation LeetCode: Optimal DivisionSeries: #findduplicates – Find duplicates from a list & Follow-up Leave a Reply Cancel replyYour email address will not be published.Comment Name Email Website