131. Palindrome PartitioningMedium

Palindrome Partitioning

MediumStringDynamic ProgrammingBacktracking·AmazonGoogle

Given a string s, split s into substrings where every substring is a palindrome. Return all possible lists of palindromic substrings.

Examples

Example 1

Inputs = "aab"

Output[["a","a","b"],["aa","b"]]

Example 2

Inputs = "a"

Output[["a"]]

1 ≤ s.length ≤ 20
s contains only lowercase English letters.

Prerequisites

Before attempting this problem, you should be comfortable with:

Backtracking - Exploring all possible partitions and undoing choices to try alternatives
Palindrome Checking - Using two pointers to verify if a substring is a palindrome

1. Backtracking - II

Intuition

We build the partition from left to right. At any starting index i, we have a simple question: "Where should I cut next?"

So we try every possible end index j from i to the end. If s[i..j] is a palindrome, it can be the next piece. We choose it (add to our current partition), then recursively solve the rest starting at j + 1. After returning, we undo the choice and try a different j.

Algorithm

Maintain: part: current list of chosen substrings. res: all palindrome partitions. Define DFS dfs(i) where i is the start index of the next substring. Base case: If i == len(s), the whole string has been partitioned → add a copy of part to res. For each j from i to len(s)-1: If s[i..j] is palindrome: Add s[i..j] to part. Recurse dfs(j + 1). Backtrack: remove last substring. Palindrome check: Two pointers l, r move inward; if mismatch → return false.

Time Complexity: O(N × 2^N) where N is the length of the string. In the worst case (e.g., all identical characters), there are 2^N-1 possible partitions, and each takes O(N) to check and build.

Space Complexity: O(N) for the recursion stack and the current partition list.

Visualizing Partition Cuts

Watch the algorithm drop a "knife" to slice the string. After each cut, it sends two pointers to verify if the sliced substring is a palindrome. If it is, the chunk is added to the Current Partition and recursion continues.

Call Stack

—

Valid Partitions

None yet...

READY—

Press ▶ or step forward to begin.

—

String (s)

Executing Code

class Solution:

    def partition(self, s: str) -> List[List[str]]:

        res, part = [], []

        def dfs(i):

            if i >= len(s):

                res.append(part.copy())

                return

            for j in range(i, len(s)):

                if self.isPali(s, i, j):

                    part.append(s[i : j + 1])

                    dfs(j + 1)

                    part.pop()

        dfs(0)

        return res

    def isPali(self, s, l, r):

        while l < r:

            if s[l] != s[r]:

                return False

            l, r = l + 1, r - 1

        return True

Common Pitfalls

Forgetting to Copy the Partition Before Adding to Results

When adding the current partition to the results list, you must add a copy of the list, not a reference to it. Since backtracking modifies the same partition list, adding the reference directly means all entries in the result will point to the same (eventually empty) list.

Incorrect Base Case in Backtracking

The base case should trigger when the starting index reaches the end of the string, indicating a complete valid partition. A common mistake is to check i > len(s) instead of i >= len(s) or i == len(s), causing missed partitions or index errors.

Discussion

…

Loading comments…

LeetMotion