{ }DevToolsDaily
ToolsInterview Prep
New
CheatsheetsDirectoryMy spaceBlog
Ctrl + K
Ask AI

Palindrome Partitioning – Solution & Complexity

Interview solutions
/
Palindrome Partitioning

Solution Walkthrough

  1. Step 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. Step 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. Step 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. Step 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. Step 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)Generate Parentheses solution (medium)Letter Combinations of a Phone Number solution (medium)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsPricingContact Us © Monkey SkatesHave kids?