{ }DevToolsDaily
ToolsInterview Prep
New
CheatsheetsChat
New
Blog
Ctrl + K

Palindrome Partitioning – Solution & Complexity

Interview solutions
/
Palindrome Partitioning

Solution Walkthrough

1. Define the search state

  • A partition is built from left to right, so the recursive state can simply be the starting index of the next substring plus the current path of chosen pieces.
  • At each step, try every possible ending index for the next piece, but only continue if that piece is a palindrome.

2. Brute-force baseline

  • The brute-force version tries every way to place separators between characters, then checks whether each produced substring is a palindrome.
  • That wastes a lot of work because the same substring gets tested repeatedly across many recursive branches.

3. Cache palindrome checks

  • Precompute is_pal[left][right] with dynamic programming: a substring is a palindrome when its ends match and its interior is also a palindrome (or has length at most 2).
  • Then the DFS can test whether a candidate piece is legal in O(1) time and keep the output in deterministic left-to-right DFS order.

4. Final solution (all languages)

The preprocessing table costs O(n^2), and the backtracking cost is proportional to the number of valid partitions produced.

def partition(s: str) -> list[list[str]]:
    n = len(s)
    is_pal = [[False] * n for _ in range(n)]
    for left in range(n - 1, -1, -1):
        for right in range(left, n):
            if s[left] == s[right] and (right - left <= 2 or is_pal[left + 1][right - 1]):
                is_pal[left][right] = True

    result = []
    path = []

    def dfs(start: int) -> None:
        if start == n:
            result.append(list(path))
            return
        for end in range(start, n):
            if not is_pal[start][end]:
                continue
            path.append(s[start:end + 1])
            dfs(end + 1)
            path.pop()

    dfs(0)
    return result

5. Common mistakes and follow-ups

  • Returning the same mutable path buffer repeatedly instead of copying it when a full partition is found.
  • Losing deterministic output order by exploring longer prefixes before shorter ones.
  • Follow-up: if the interviewer asks for minimum cuts only, this turns into a dynamic-programming optimization problem instead of an output-all backtracking problem.

FAQ

See also

Practice Palindrome Partitioning online (run code in the browser)Decode Ways solution (medium)Edit Distance solution (hard)Letter Combinations of a Phone Number solution (medium)Longest Palindromic Substring solution (medium)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsPricingContact Us © Monkey SkatesHave kids?