Palindrome Partitioning

PracticeNeetCode ↗LeetCode ↗

Given a string s, split it into substrings so every substring is a palindrome. Return all possible ways to do this.

Example

Input s = "aab"

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

Key Pointers

At every position, try every possible "next cut" and only recurse into it if the substring up to that cut is a palindrome — invalid cuts are pruned immediately, never explored further.
A slice-equals-its-reverse check (sub == sub[::-1]) is enough to test for a palindrome; no separate DP table is needed unless performance demands it.
A full partition is complete exactly when the start index reaches the end of the string.

Step-by-Step Analysis

Define isPalindrome(sub) using sub == sub[::-1].
Define backtrack(start): if start == len(s), record a copy of path.
Loop end from start + 1 to len(s) + 1: let sub = s[start:end].
If isPalindrome(sub), append sub to path, recurse with backtrack(end), then pop.
Call backtrack(0) and return the result.

Complexity

Time: O(n · 2ⁿ) worst case — Space: O(n) recursion depth

Code

def partition(s: str) -> list[list[str]]:
    result = []
    path = []

    def isPalindrome(sub: str) -> bool:
        return sub == sub[::-1]

    def backtrack(start: int) -> None:
        if start == len(s):
            result.append(path[:])
            return
        for end in range(start + 1, len(s) + 1):
            sub = s[start:end]
            if isPalindrome(sub):
                path.append(sub)
                backtrack(end)
                path.pop()

    backtrack(0)
    return result

Code Explanation

How the solution above works, piece by piece.

backtrack(start) decides how to cut the rest of the string, s[start:].
When start == len(s), the whole string is split into palindromes: save a copy of path.
Try every end position: sub = s[start:end] is the next piece.
Only if sub is a palindrome, add it, recurse from end, then pop. Non-palindromes prune the branch immediately.
Worst case O(n · 2ⁿ): there are up to 2ⁿ⁻¹ ways to cut a string of length n.

Visual Walkthrough

The recursion tree for s = "aab":

Each branch cuts off the next piece of the string, but only if that piece is a palindrome. When the whole string has been cut, the pieces form one answer: a|a|b and aa|b.

complete partition

Video Explanation

NeetCode — Backtracking, LeetCode 131