Domain 2MediumCORE

Palindrome Partitioning

We are given a string s and need to return every possible way to split this string into substrings such that each substring is a palindrome. The output format requires returning all valid partitions as a list of lists (e.g., [['a', 'b'], ['ab']]).

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Dynamic Programming#Backtracking#Depth-first Search

131. Palindrome Partitioning

Model: qwen3.5:9b
Topics: Dynamic Programming,Backtracking,Depth-first Search
FAANG asked: 1
Acceptance rate: 52.6%


Problem Breakdown

We are given a string s and need to return every possible way to split this string into substrings such that each substring is a palindrome. The output format requires returning all valid partitions as a list of lists (e.g., [["a", "b"], ["ab"]]).

Key constraints:

  1. String length between 1 and 16.
  2. Only lowercase English letters.

Implicit considerations: Since single characters are always palindromes, there will never be an empty result set unless the input is invalid (which isn’t possible per constraints). The maximum number of partitions grows exponentially with string length because every character can theoretically start a new partition or extend the current one if it remains a palindrome.

Intuition

The core task here is exploring all combinations of cuts between characters in s. This structure strongly suggests Backtracking (Depth-First Search).

If we try to solve this iteratively, managing state for partial partitions becomes messy. Instead, I’ll treat the string as being built from left to right. At any point, say index i, I can choose a substring starting at i and ending at some index j. If that slice is a palindrome, it’s a valid piece of our partition.

Why not brute force? A naive approach might check every possible cut combination without validating the palindrome property efficiently during traversal. However, since we need to return all partitions, pruning isn’t about skipping solutions (like in subset sum), but rather ensuring we only recurse on paths that satisfy the palindrome constraint immediately. The “brute-force” here is actually necessary because there’s no simple DP state for generating all combinations unless we memoize existence checks, which doesn’t help with output generation directly given the constraints (N≤16N \le 16).

Approach

I will implement a recursive backtracking function backtrack(start_index).

  1. State: Maintain a current list of strings (path) representing the partition built so far for this recursion branch.
  2. Loop: Iterate through all possible end indices i starting from start_index to the end of string s.
  3. Check: Extract substring sub = s[start:i+1]. Check if it is a palindrome (using slicing comparison).
  4. Recurse: If valid, append sub to path, call backtrack(i + 1), then pop from path (backtracking step).
  5. Base Case: When the loop index reaches the end of string length, we have successfully partitioned the whole string. Append a copy of path to our global results list and return.

Complexity Analysis

  • Time Complexity: O(N⋅2N−1)O(N \cdot 2^{N-1}). In the worst case (e.g., input “aaaa”), every substring is a palindrome, resulting in roughly 2N−12^{N-1} valid partitions. For each partition path, we perform string slicing and comparison which takes linear time relative to the slice length (O(N)O(N)). While often loosely cited as exponential or related to Bell numbers for general cases, this bound accurately reflects the maximum number of recursive calls times operation cost per call.
  • Space Complexity: O(N)O(N) for recursion stack depth plus O(K⋅N2)O(K \cdot N^2) where K is number of partitions (output storage), as Python lists store references to strings created during backtracking.

Solution

from typing import List

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        res = []
        
        # Helper function for palindrome check using slicing
        def is_palindrome(sub):
            return sub == sub[::-1]
            
        def backtrack(start_index, path):
            # Base case: if we've reached the end of string
            if start_index >= len(s):
                res.append(path[:])  # Append a copy to avoid reference issues
                return
            
            for i in range(start_index, len(s)):
                sub = s[start_index : i + 1]
                
                # Optimization: Only recurse if current substring is palindrome
                if is_palindrome(sub):
                    path.append(sub)
                    backtrack(i + 1, path)
                    path.pop()

        backtrack(0, [])
        return res

Edge Cases Handled

  • Single Character String: The loop runs once for the single character (which is a palindrome), recurses to end immediately, and returns [["a"]]. Correct.
  • All Same Characters (“aaaa”): Generates all possible partitions where every substring s[i:j] is valid palindromic segments. Code handles this naturally via loop bounds.
  • Empty String: Constraints say length >= 1, but if passed empty string, the base case triggers immediately returning [[]]. (Though technically invalid per constraints).