Palindrome Partitioning

Problem

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

Example 1:

Input: s = "aab"
Output: [["a","a","b"],["aa","b"]]

Example 2:

Input: s = "a"
Output: [["a"]]

Constraints:

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

Solution

Approach: Backtracking with Palindrome Check

The key insight is to try partitioning at every possible position, checking if each substring is a palindrome before recursing.

Implementation

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        result = []

        def is_palindrome(string):
            return string == string[::-1]

        def backtrack(start, path):
            if start == len(s):
                result.append(path[:])
                return

            for end in range(start + 1, len(s) + 1):
                substring = s[start:end]
                if is_palindrome(substring):
                    path.append(substring)
                    backtrack(end, path)
                    path.pop()

        backtrack(0, [])
        return result

Optimized with DP:

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        n = len(s)
        result = []

        # Build palindrome DP table
        is_palindrome = [[False] * n for _ in range(n)]
        for i in range(n):
            is_palindrome[i][i] = True
        for length in range(2, n + 1):
            for i in range(n - length + 1):
                j = i + length - 1
                if s[i] == s[j]:
                    is_palindrome[i][j] = (length == 2 or is_palindrome[i+1][j-1])

        def backtrack(start, path):
            if start == n:
                result.append(path[:])
                return

            for end in range(start, n):
                if is_palindrome[start][end]:
                    path.append(s[start:end+1])
                    backtrack(end + 1, path)
                    path.pop()

        backtrack(0, [])
        return result

Complexity Analysis

Basic Approach:

Time Complexity: O(n * 2^n), where n is the length of string. We explore 2^n partitions and check palindrome for each.
Space Complexity: O(n) for recursion depth.

DP Optimized:

Time Complexity: O(n * 2^n) for backtracking, but palindrome checks are O(1).
Space Complexity: O(n²) for DP table + O(n) recursion.

Key Insights

Partition Points: We try making a cut after every position and check if the substring before the cut is a palindrome.
Complete Partitioning: Base case is when we’ve consumed the entire string (start == len(s)).
Palindrome Check: We can check palindromes naively in O(n), or precompute all palindromes using DP in O(n²).
Backtracking Pattern: Try each valid partition, recurse for remaining string, then backtrack.
All Partitions: Unlike other problems where we find one solution, we need to explore all possible partitions.