Minimum Palindromic Partitions

From Daily Coding Problem / LeetCode:

Given a string, split it into as few strings as possible such that each string is a palindrome. For example, given the input string "racecarannakayak", return ["racecar", "anna", "kayak"].

Input: "racecarannakayak"
Output: ["racecar", "anna", "kayak"]

Expanding from Midpoints

Where palindrome-related problems are concerned, a common pattern is to expand from possible midpoints.

def expand_from_middle(left, right):
    nonlocal s
    length = 0 
   
    while 0 <= left and right <= len(s) - 1:
        if s[left] == s[right]:
            length = max(length, right-left+1)
            left -= 1
            right += 1

expand_from_middle(i, i)
expand_from_middle(i, i+1)

A caveat is that this usually only works well when you’re guaranteed a valid input. Problems which, for instance, require you to transform inputs into palindromes or detect strings that are k characters away (from becoming palindromes) benefit less from this approach.

The question implies that a palindromic split is possible, so using something like expand_from_middle() for this problem is fine.

Dynamic Programming for Palindromes

Before proceeding further, let’s think about what this question wants us to do. You can break the requirements down into two aspects:

• Determining the palindromic chunks in the string
• Optimising for the minimum number of partitions

Since we’re optimising for a minimum, there’s a good chance we’ll need to use dynamic programming. Let’s first initialise an array that will persist some kind of information at each string index:

DP = [None for _ in range(len(s))]

Now what exactly do we store at each index?

• To keep track of the palindromic chunks we’ve seen, we need to log the position of each palindromic substring. Specifically, this means storing their beginning and ending indices.
• To optimise for the minimum number of partitions, we need to log the number of palindromes we’ve seen.

With these two things in mind, let’s make DP[i] contain two values rather than one.

For a given palindromic substring that ends at i (inclusive), we store:

• the start index of the substring
• the count, which indicates how many palindromic strings are connected to this substring (from the left)

# A DP entry item
Entry = collections.namedtuple('Entry', ('start', 'count'))

# Initial state:
# Every char is a length one palindrome
# 0 to i contains i+1 length one palindromes
DP = [Entry(i, i+1) for i in range(len(s))]

Now that we know what information to store and how to store it, let’s start writing out our subroutine for finding palindromes. As mentioned earlier, we do so by expanding leftward and rightward from possible palindromic midpoints. Pay attention to how DP[i] is updated below:

def expand(left, right):
    nonlocal s:

    if s[left] != s[right]:
        return
    
    while 0 <= left and right <= len(s)- 1:
        if s[left] == s[right]:
            # Generate entry for this palindrome
            entry = Entry(
                left,
                DP[left-1].count + 1 if left-1 >= 0 else 1
            )

            # Compare new entry with existing one,
            # *optimise* for minimum count
            DP[right] = min([
                DP[right], entry
            ], key=lambda e: e.count)

            left -= 1
            right += 1
        else:
            break

Using the expand() function in our overall algorithm is easy. We just have to call it from every possible palindromic midpoint (or pair of midpoints):

def partition(s):
    DP = [Entry(i, i+1) for i in range(len(s))]

    def expand(left, right):
        # Move pointers outward, update DP array
        # ...

    for i in range(len(s)):
        expand(i, i)
        if i + 1 <= len(s) - 1:
            expand(i, i+1)

Once our DP array has been populated, we’ll need to traverse it linearly to generate our resultant list of palindromic words. We traverse it in reverse since each DP[i] gives us the start index.

def partition(s):
    # Populate DP array
    # ...

    res, i = [], len(s) - 1
    while i > 0:
        res.append(s[DP[i].start:i+1])
        i = DP[i].start - 1

    return res[::-1]

Given a string of length n, our algorithm runs in O(n) space and O(n^2) time.

With that, we’ve solved the Palindromic Partitions problem 🎹🎹.

Full Solution

import collections

Entry = collections.namedtuple('Entry', ('start', 'count'))

def partition(s):
    DP = [Entry(i, i+1) for i in range(len(s))]
    
    def expand(left, right):
        nonlocal s
        
        if s[left] != s[right]:
            return
        
        while 0 <= left and right <= len(s) - 1:
            if s[left] == s[right]:
                entry = Entry(
                    left,
                    DP[left-1].count + 1 if left - 1 >= 0 else 1
                )

                DP[right] = min([
                    DP[right], entry
                ], key=lambda e: e.count)

                left -= 1
                right += 1
            else:
                break
        
    for i in range(len(s)):
        expand(i, i)
        if i + 1 <= len(s) - 1:
            expand(i, i+1)
    
    
    res, i = [], len(s)-1
    
    while i >= 0:
        entry = DP[i]
        res.append(s[entry.start:i+1])
        i = entry.start - 1
    
    return res[::-1]