Palindrome Partitioning

Interview Problem Interview Medium Constraint Satisfaction String Backtracking

Checking your account…

Loading the interactive Interview workspace.If it does not appear, the problem and learning material remain readable, but browser execution is unavailable.Reload Interview workspace

Problem

Implement Solution.partition(text). Return every ordered partition covering the full string where each segment reads the same forward and backward. Partition order does not matter.

Starter code

class Solution:
    def partition(self, text):
        pass

Test cases

two-partitions

{
  "args": [
    "aab"
  ]
}

Expected: [["a","a","b"],["aa","b"]]

Wizard outline

Step 1: Initialize Solution.partition
Replace the empty starter with the first real state owned by Solution.partition. A small, named state is easier to verify than a complete algorithm. Establish it before adding the branch or loop that changes it.
Step 2: Assemble the primary transition
Extend the initialized state with the next contiguous part of the popular solution. The transition explains how one input element or operation changes the state; boundaries are easier to reason about after this invariant is visible.
Step 3: Pass the Single case
Complete the readable core algorithm for one representative Interview case. Choose the next prefix, prune non-palindromes, and recurse from its end.
Step 4: Harden the Non Palindrome Whole boundary
Repair the reviewed boundary and pass the complete submission contract. Every emitted path consists only of checked palindromes and consumes the full string. Every valid partition has a first segment considered by the loop, then is found inductively in the corresponding suffix search.

Footguns and prerequisites

Order inside a partition is meaningful because segments must reconstruct the original string.
recursion and backtracking

Reviewed references

Practice prerequisites

Complete One Backtracking Frame(opens in a new tab)
Complete One Backtracking Frame isolates before expanding each choice, path equals the original caller-owned prefix; every emitted candidate contains exactly one additional element. That focused state discipline is required when implementing palindrome partitioning as a complete Interview Problem.

Recommended approach and implementation

At each start index, try every ending prefix, recurse only when that prefix is a palindrome, and emit when start reaches the string length.

Why it works: Every emitted path consists only of checked palindromes and consumes the full string. Every valid partition has a first segment considered by the loop, then is found inductively in the corresponding suffix search.

class Solution:
    def partition(self, text):
        """
        Checkpoint 1: initialize the state owned by this Interview contract.
        Checkpoint 2: assemble the primary transition without hiding the boundary.
        """
        result = []
        path = []
        def backtrack(start):
            if start == len(text):
                result.append(path[:])
                return
            for end in range(start + 1, len(text) + 1):
                segment = text[start:end]
                if segment != segment[::-1]:
                    continue
                path.append(segment)
                backtrack(end)
                path.pop()
        backtrack(0)
        return result