How do you solve Palindrome Partitioning?

Use a backtracking algorithm that starts at index 0 and tries all substrings s[i:j+1]. For each substring, check if it is a palindrome using a helper function. If it is, append it to the current partition and recurse from j+1. When the recursion index reaches the end of the string, add a copy of the current partition to the results. Backtrack by removing the last substring before trying the next. This approach enumerates all valid palindrome partitions efficiently.

What pattern does Palindrome Partitioning use?

The Pattern: Backtracking (State Restoration) The Heuristic: For problems requiring enumeration of all valid partitions or combinations, use backtracking with early pruning by validating partial solutions before recursing, and always restore state after recursion to explore alternative branches.

Palindrome Partitioning — Backtracking

Q: What is the time complexity of Palindrome Partitioning?

O(N * 2^N). There are up to 2^(N-1) ways to partition a string of length N, and palindrome checking for each substring takes O(N) in the worst case, leading to O(N * 2^N) complexity.

Problem

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

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

Example

Input: s = "aab"

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

The brute-force approach would try all possible partitions of the string and check if each substring is a palindrome, which is exponential and inefficient. The optimal approach uses backtracking to build partitions incrementally, pruning paths early by checking palindrome validity. Starting at index 0, the algorithm tries substrings "a", "aa", and "aab". "a" is a palindrome, so it recurses from index 1. From index 1, it tries "a" and "ab"; "a" is palindrome, recurse from index 2. At index 2, "b" is palindrome, so the partition ["a","a","b"] is added. Backtracking then tries "aa" from index 0, which is palindrome, recurses from index 2, and adds ["aa","b"]. The substring "aab" is not palindrome, so it is skipped. This systematic exploration ensures all valid partitions are found without redundant checks.

Approach

Straightforward Solution

A brute-force approach generates all possible partitions and checks each substring for palindrome validity after the fact. This leads to exponential time complexity with redundant palindrome checks and no pruning.

Core Observation

The problem requires enumerating all partitions of a string where each substring is a palindrome. This naturally forms a decision tree where at each index, the algorithm chooses a substring to include if it is a palindrome, then recurses on the remainder.

Path to Optimal

Preview

The key insight is to integrate palindrome checking into the backtracking process, pruning invalid partitions early. By checking palindrome validity on the fly and only recursing on valid substrings, the algorithm avoids exploring invalid branches…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Use a backtracking algorithm that starts at index 0 and tries all substrings s[i:j+1]. For each substring, check if it is a palindrome using a helper function…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(N * 2^N)

There are up to 2^(N-1) ways to partition a string of length N, and palindrome checking for each substring takes O(N) in the worst case, leading to O(N * 2^N) complexity.

Space

O(N)

The recursion stack and the current partition list can grow up to O(N) in the worst case, excluding the output list which can be exponentially large.

Solution

Python

1class Solution:
  def partition(self, s: str) -> list[list[str]]:
      res = []
      part = []
5
      def dfs(i):
          if i >= len(s):
              res.append(part.copy())
              return
          
          for j in range(i, len(s)):
              if self.is_palindrome(s, i, j):
                  part.append(s[i:j+1])
                  dfs(j + 1)
                  part.pop()
      
      dfs(0)
      return res
19
  def is_palindrome(self, s, l, r):
      while l < r:
          if s[l] != s[r]:
              return False
          l, r = l + 1, r - 1
      return True

Step-by-Step Solution

1

Initialize Result and Current Partition Containers

3res = []
4part = []

Objective

To prepare storage for all valid palindrome partitions and the current working partition during recursion.

Key Insight

The result list accumulates all valid partitions found, while the current partition list tracks the substrings chosen so far in the current recursive path. These two data structures enable the backtracking framework to build and store solutions incrementally.

Interview Quick-Check

Core Logic

The result list stores all valid partitions, while the current partition list represents the current path in the recursion tree.

State & Boundaries

The current partition list is cleared and rebuilt during backtracking to explore all possible partitions.

2

Explore Substrings and Backtrack on Palindromic Partitions

To recursively explore all substrings starting at the current index, append palindromic substrings to the current partition, recurse, and backtrack to explore alternatives.

3

Check Palindrome Validity for Substrings

To verify whether a substring s[l:r] is a palindrome by comparing characters from both ends inward.

2 more steps with full analysis available on Pro.

Line Analysis

This solution has 4 Critical lines interviewers watch for.

Line 15 Critical

part.pop()

Remove the last substring to backtrack and restore state.

This state restoration is the single most critical line in backtracking; it ensures that after exploring one branch, the algorithm can correctly explore others without contamination from previous choices.

Line 8 Critical

res.append(part.copy())

Add a copy of the current partition to the results list.

Copying is essential because the current partition list is mutable and will be modified during backtracking; storing a copy preserves the valid solution.

Line 12 Critical

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

Check if the substring s[i:j+1] is a palindrome.

This conditional prunes the search space by only exploring partitions that include palindromic substrings, avoiding invalid branches.

Full line-by-line criticality + rationale for all 18 lines available on Pro.

Test Your Understanding

Why is it necessary to backtrack (remove the last substring) after each recursive call in this algorithm?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Palindrome Partitioning from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Palindrome Partitioning drill

or drill a free problem

1	`class Solution:`
2	`def partition(self, s: str) -> list[list[str]]:`
3	`res = []`
4	`part = []`
5
6	`def dfs(i):`
7	`if i >= len(s):`
8	`res.append(part.copy())`
9	`return`
10
11	`for j in range(i, len(s)):`
12	`if self.is_palindrome(s, i, j):`
13	`part.append(s[i:j+1])`
14	`dfs(j + 1)`
15	`part.pop()`
16
17	`dfs(0)`
18	`return res`
19
20	`def is_palindrome(self, s, l, r):`
21	`while l < r:`
22	`if s[l] != s[r]:`
23	`return False`
24	`l, r = l + 1, r - 1`
25	`return True`