Generated by Codex with GPT-5

Difficulty: MEDIUM
Problem: Palindrome Partitioning

Problem gist

The input is a string s. The task is to return every possible way to split s into non-empty substrings such that every chosen substring is a palindrome.

For example, "aab" can be split as ["a", "a", "b"] or ["aa", "b"]. Both are valid because every piece reads the same forward and backward. A split like ["a", "ab"] is invalid because "ab" is not a palindrome.

The important detail is that this is not asking for one best split. It asks for all valid splits, so the output itself may be exponential in the length of the string.

How to derive the solution

Think of building a partition from left to right. At position start, choose an ending position end, take s[start:end + 1], and continue from end + 1 only if that substring is a palindrome.

That gives a natural backtracking tree:

1. If start has reached the end of the string, the current list of pieces is one complete answer.
2. Otherwise, try every possible next substring starting at start.
3. Keep the substring only when it is a palindrome.
4. Recurse on the remaining suffix.
5. Remove the substring and try the next choice.

The costly part is palindrome checking. If each check scans the substring, the same ranges get rechecked many times across different branches. A cleaner approach is to precompute a table where is_palindrome[i][j] says whether s[i:j + 1] is a palindrome.

The recurrence is simple: s[i:j + 1] is a palindrome if the two ends match and the inside substring is also a palindrome. The inside is empty or one character when j - i <= 2, so those cases are directly valid when the ends match.

After that table is built, each backtracking decision can test palindromes in O(1).

The palindrome table costs O(n^2) time and space. The backtracking still has exponential worst-case output, especially for strings like "aaaaa" where nearly every substring is a palindrome. The practical complexity is O(n^2 + n * number_of_partitions) time, because copying each completed partition costs up to O(n), and O(n^2) extra space for the table plus recursion/path storage.

Python solution

from typing import List


class Solution:
    def partition(self, s: str) -> List[List[str]]:
        """Return all palindrome partitions of s."""
        palindrome_table = self._build_palindrome_table(s)
        partitions: List[List[str]] = []
        current_partition: List[str] = []

        def backtrack(start_index: int) -> None:
            if start_index == len(s):
                partitions.append(current_partition.copy())
                return

            for end_index in range(start_index, len(s)):
                if not palindrome_table[start_index][end_index]:
                    continue

                current_partition.append(s[start_index : end_index + 1])
                backtrack(end_index + 1)
                current_partition.pop()

        backtrack(0)
        return partitions

    @staticmethod
    def _build_palindrome_table(s: str) -> List[List[bool]]:
        """Precompute whether every substring s[start:end + 1] is a palindrome."""
        length = len(s)
        palindrome_table = [[False] * length for _ in range(length)]

        for start in range(length - 1, -1, -1):
            for end in range(start, length):
                ends_match = s[start] == s[end]
                inner_is_palindrome = end - start <= 2 or palindrome_table[start + 1][end - 1]
                palindrome_table[start][end] = ends_match and inner_is_palindrome

        return palindrome_table

Interview follow-ups

What if the interviewer asks for only the minimum number of cuts?

This becomes LeetCode 132, Palindrome Partitioning II. The output is no longer every partition; it is the fewest cuts needed so that every piece is a palindrome. Reuse the same is_palindrome table, then run dynamic programming over prefixes or suffixes.

Let min_cuts[end] mean the minimum cuts needed for s[:end + 1]. For every start <= end, if s[start:end + 1] is a palindrome, then the partition can either use no cut when start == 0, or use min_cuts[start - 1] + 1. Taking the minimum over all starts gives the answer.

This works because the last palindrome block fully determines which earlier prefix remains. The complexity is O(n^2) time and O(n^2) space with the palindrome table, or O(n^2) time and O(n) cuts space if palindrome checks are expanded around centers carefully.

What if the interviewer asks whether at least one valid partition exists under extra rules?

Without extra rules, at least one partition always exists because every single character is a palindrome. With extra constraints, such as requiring exactly k pieces or requiring each piece to have length at least m, the problem becomes a constrained search or dynamic programming problem.

For exactly k pieces, define a state like (start_index, pieces_used) and ask whether the suffix from start_index can be completed with the remaining number of pieces. The transition tries every palindromic next substring that leaves enough characters for the remaining pieces. Memoizing this state avoids recomputing the same suffix decisions.

The tradeoff is that this version may be polynomial if it only asks for existence, but it becomes output-sensitive again if it asks to list all constrained partitions.

What if the interviewer asks for results in lexicographic order?

The standard left-to-right loop already tries shorter substrings before longer substrings from the same start. That does not always guarantee global lexicographic ordering of the list-of-lists result under every comparison rule.

If strict lexicographic output is required, the safest approach is to generate all valid partitions and sort them using Python’s normal list comparison. That costs additional time proportional to sorting the output, which may be acceptable because the output can already be exponential.

If memory is a concern, the interviewer may expect a custom traversal order that emits partitions in sorted order without a final sort. That is harder because choices at earlier positions dominate ordering, so the traversal must define and follow the exact comparison rule.

What if the interviewer asks how to reduce memory usage?

The O(n^2) palindrome table is fast and simple, but it stores every substring answer. To reduce memory, palindrome checks can be done on demand with memoization, storing only ranges that are actually reached by the search. In many strings this still trends toward O(n^2), but it may save space when the search prunes heavily.

Another option is to expand around each center and build an adjacency list of palindromic edges: for every palindromic substring s[i:j + 1], store that j + 1 is reachable from i. Backtracking then follows those edges. This is still O(n^2) in the worst case, but it can be a more direct representation of the decision graph.

The key interview point is that memory can be shifted around, but all-palindrome-partition generation cannot avoid exponential output in the worst case.