Skip to content

Prepare For Coder Interview – Denny

  • Basic
  • Medium
  • Hard
  • Architect
  • Life

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
}
linkedin
github
slack

Post Views: 0
Posted in MediumTagged #palindrome, #twopointer, rollinghash

Post navigation

LeetCode: Optimal Division
Series: #findduplicates – Find duplicates from a list & Follow-up

Leave a Reply Cancel reply

Your email address will not be published.

Tags

#array #backtracking #bfs #binarytree #bitmanipulation #blog #classic #codetemplate #combination #dfs #dynamicprogramming #game #graph #greedy #heap #inspiring #interval #linkedlist #manydetails #math #palindrome #recursive #slidingwindow #stack #string #subarray #trie #twopointer #twosum binarysearch editdistance hashmap intervaldp knapsack monotone oodesign presum rectangle redo review rotatelist series sql treetraversal unionfind

Recent Posts

  • a
  • a
  • a
  • a
  • a

Recent Comments

    Archives

    Categories

    • Amusing
    • Basic
    • Easy
    • Hard
    • Life
    • Medium
    • Resource
    • Review
    • Series
    • Uncategorized
    Proudly powered by WordPress | Theme: petals by Aurorum.