Solution: Palindromic Partitioning

Grokking Dynamic Programming Patterns for Coding Interviews

Ask Author

Back to course home

0% completed

Vote For New Content

Solution: Palindromic Partitioning

Table of Contents

Contents are not accessible

Problem Statement

Given a string, we want to cut it into pieces such that each piece is a palindrome. Write a function to return the minimum number of cuts needed.

Example 1:

Input: "abdbca"
Output: 3
Explanation: Palindrome pieces are "a", "bdb", "c", "a".

Example 2:

Input: = "cddpd"
Output: 2
Explanation: Palindrome pieces are "c", "d", "dpd".

Example 3:

Input: = "pqr"
Output: 2
Explanation: Palindrome pieces are "p", "q", "r".

Example 4:

Input: = "pp"
Output: 0
Explanation: We do not need to cut, as "pp" is a palindrome.

Constraints:

1 <= st.length <= 16
s contains only lowercase English letters.

Basic Solution

This problem follows the "Longest Palindromic Subsequence" pattern and shares a similar approach as that of the "Longest Palindromic Substring".

The brute-force solution will be to try all the substring combinations of the given string. We can start processing from the beginning of the string and keep adding one character at a time. At any step, if we get a palindrome, we take it as one piece and recursively process the remaining length of the string to find the minimum cuts needed.

Here is the code:

Python3

. . . .

The time complexity of the above algorithm is exponential $O(2^n)$ , where 'n' is the length of the input string. The space complexity is $O(n)$ which is used to store the recursion stack.

Top-down Dynamic Programming with Memoization

We can memoize both functions findMPPCutsRecursive() and isPalindrome(). The two changing values in both these functions are the two indexes; therefore, we can store the results of all the subproblems in a two-dimensional array. (alternatively, we can use a hash-table).

Here is the code:

Python3

. . . .

Bottom-up Dynamic Programming

The above solution tells us that we need to build two tables, one for the isPalindrome() and one for finding the minimum cuts needed.

If you remember, we built a table in the Longest Palindromic Substring (LPS) chapter that can tell us what substrings (of the input string) are palindrome. We will use the same approach here to build the table required for isPalindrome(). For example, here is the final output from LPS for "cddpd". From this table we can clearly see that the substring(2,4) => 'dpd' is a palindrome:

To build the second table for finding the minimum cuts, we can iterate through the first table built for isPalindrome(). At any step, if we get a palindrome, we can cut the string there. Which means minimum cuts will be one plus the cuts needed for the remaining string.

Here is the code for the bottom-up approach:

Python3

. . . .

The time and space complexity of the above algorithm is $O(n^2)$ , where 'n' is the length of the input string.

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible