Day 39

Day 39: Palindrome Partitioning

Advanced 12 min

39/60 Days

Palindrome Partitioning#

Welcome to Day 39 of our 60 Days of Coding Algorithm Challenge! Today, we’ll explore the Palindrome Partitioning problem, which combines string manipulation with dynamic programming concepts.

What is Palindrome Partitioning?#

Palindrome Partitioning is the problem of dividing a string into substrings, where each substring is a palindrome. A palindrome is a string that reads the same backward as forward.

Problem Statement#

Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s.

Naive Recursive Approach#

Let’s start with a naive recursive implementation:

 1def is_palindrome(s, start, end):
 2    while start < end:
 3        if s[start] != s[end]:
 4            return False
 5        start += 1
 6        end -= 1
 7    return True
 8
 9def palindrome_partition_recursive(s):
10    def backtrack(start, path):
11        if start == len(s):
12            result.append(path[:])
13            return
14        
15        for end in range(start, len(s)):
16            if is_palindrome(s, start, end):
17                path.append(s[start:end+1])
18 …

Palindrome Partitioning#

Welcome to Day 39 of our 60 Days of Coding Algorithm Challenge! Today, we’ll explore the Palindrome Partitioning problem, which combines string manipulation with dynamic programming concepts.

What is Palindrome Partitioning?#

Palindrome Partitioning is the problem of dividing a string into substrings, where each substring is a palindrome. A palindrome is a string that reads the same backward as forward.

Problem Statement#

Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s.

Naive Recursive Approach#

Let’s start with a naive recursive implementation:

 1def is_palindrome(s, start, end):
 2    while start < end:
 3        if s[start] != s[end]:
 4            return False
 5        start += 1
 6        end -= 1
 7    return True
 8
 9def palindrome_partition_recursive(s):
10    def backtrack(start, path):
11        if start == len(s):
12            result.append(path[:])
13            return
14        
15        for end in range(start, len(s)):
16            if is_palindrome(s, start, end):
17                path.append(s[start:end+1])
18                backtrack(end + 1, path)
19                path.pop()
20    
21    result = []
22    backtrack(0, [])
23    return result
24
25# Example usage
26s = "aab"
27print(f"Palindrome partitions of '{s}': {palindrome_partition_recursive(s)}")

This approach has a time complexity of O(n * 2^n), where n is the length of the string, making it inefficient for longer strings.

Dynamic Programming Approach#

We can improve the efficiency using Dynamic Programming to precompute palindrome information.

 1def palindrome_partition_dp(s):
 2    n = len(s)
 3    # dp[i][j] is True if s[i:j+1] is a palindrome
 4    dp = [[False] * n for _ in range(n)]
 5    
 6    # All substrings of length 1 are palindromes
 7    for i in range(n):
 8        dp[i][i] = True
 9    
10    # Check for substrings of length 2 and more
11    for length in range(2, n + 1):
12        for i in range(n - length + 1):
13            j = i + length - 1
14            if length == 2:
15                dp[i][j] = (s[i] == s[j])
16            else:
17                dp[i][j] = (s[i] == s[j]) and dp[i+1][j-1]
18    
19    def backtrack(start, path):
20        if start == n:
21            result.append(path[:])
22            return
23        
24        for end in range(start, n):
25            if dp[start][end]:
26                path.append(s[start:end+1])
27                backtrack(end + 1, path)
28                path.pop()
29    
30    result = []
31    backtrack(0, [])
32    return result
33
34# Example usage
35s = "aab"
36print(f"Palindrome partitions of '{s}': {palindrome_partition_dp(s)}")

This approach has a time complexity of O(n * 2^n) in the worst case, but it’s generally faster due to the precomputation of palindrome information.

Optimized Solution: Manacher’s Algorithm#

For very long strings, we can use Manacher’s Algorithm to find all palindromic substrings in O(n) time, which can then be used to optimize our partitioning:

 1def manacher(s):
 2    t = '#' + '#'.join(s) + '#'
 3    n = len(t)
 4    p = [0] * n
 5    c = r = 0
 6    for i in range(1, n-1):
 7        mirror = 2*c - i
 8        if i < r:
 9            p[i] = min(r - i, p[mirror])
10        while i + (1 + p[i]) < n and i - (1 + p[i]) >= 0 and t[i + (1 + p[i])] == t[i - (1 + p[i])]:
11            p[i] += 1
12        if i + p[i] > r:
13            c, r = i, i + p[i]
14    return p
15
16def palindrome_partition_manacher(s):
17    p = manacher(s)
18    n = len(s)
19    is_palindrome = [[False] * n for _ in range(n)]
20    for i in range(n):
21        for j in range(i, n):
22            center = i + j + 1
23            radius = j - i
24            if p[center] >= radius:
25                is_palindrome[i][j] = True
26    
27    def backtrack(start, path):
28        if start == n:
29            result.append(path[:])
30            return
31        
32        for end in range(start, n):
33            if is_palindrome[start][end]:
34                path.append(s[start:end+1])
35                backtrack(end + 1, path)
36                path.pop()
37    
38    result = []
39    backtrack(0, [])
40    return result
41
42# Example usage
43s = "aab"
44print(f"Palindrome partitions of '{s}': {palindrome_partition_manacher(s)}")

This approach has a time complexity of O(n) for palindrome precomputation and O(2^n) for partitioning in the worst case.

Applications of Palindrome Partitioning#

Text processing and analysis
Bioinformatics (DNA sequence analysis)
Natural Language Processing
Cryptography and steganography

Exercise#

Modify the algorithm to find the minimum number of cuts needed to partition a string into palindromes.
Implement a function that finds the longest palindromic subsequence in a string using dynamic programming.
Create an algorithm that generates all possible palindromes that can be formed by rearranging the characters of a given string.

Summary#

Today, we explored the Palindrome Partitioning problem, which combines string manipulation with dynamic programming concepts. We implemented various approaches, from naive recursion to optimized solutions using Manacher’s Algorithm.

Understanding Palindrome Partitioning and its solutions provides valuable insights into string manipulation techniques and their applications in various fields of computer science.

Tomorrow, we’ll dive into another interesting problem: the Longest Palindromic Substring. Stay tuned!

Solution#

The worked solution is a lifetime-access perk. Unlock all 60 solutions. Already purchased? Log in to view it.

Show the solution

Exercise 1: minimum number of cuts needed to partition a string into palindromes.

 1def min_palindrome_cuts(s):
 2    n = len(s)
 3    if n == 0:
 4        return 0
 5    # pal[i][j] is True if s[i:j+1] is a palindrome
 6    pal = [[False] * n for _ in range(n)]
 7    for i in range(n):
 8        pal[i][i] = True
 9    for length in range(2, n + 1):
10        for i in range(n - length + 1):
11            j = i + length - 1
12            if s[i] == s[j] and (length == 2 or pal[i+1][j-1]):
13                pal[i][j] = True
14
15    # cuts[i]: minimum cuts needed for prefix s[0:i+1]
16    cuts = [0] * n
17    for i in range(n):
18        if pal[0][i]:
19            cuts[i] = 0
20        else:
21            cuts[i] = min(cuts[j] + 1 for j in range(i) if pal[j+1][i])
22    return cuts[n - 1]
23
24# Example usage
25print(f"Minimum cuts for 'aab': {min_palindrome_cuts('aab')}")     # 1  -> "aa" | "b"
26print(f"Minimum cuts for 'aabaa': {min_palindrome_cuts('aabaa')}") # 0  -> already a palindrome

We first precompute the palindrome table with the same interval DP shown above. Then cuts[i] is the minimum number of cuts for the prefix ending at i. If the whole prefix is already a palindrome, zero cuts are needed. Otherwise we try every last piece s[j+1..i] that is a palindrome and take one more cut than the best solution for the prefix ending at j. Time complexity is O(n^2) and space complexity is O(n^2) for the palindrome table.

Keep your momentum going

Create a free account to unlock the full lesson, all 60 days, and track your progress as you go.