Skip to content

Volume ITechnology

4.18.7 — Palindrome Partitioning ​

LeetCode 131 · Medium · ★ Blind 75

The problem ​

Cut the string into pieces so that every piece is a palindrome. Return all possible ways.

"aab"  →  [["a","a","b"], ["aa","b"]]

The string is at most 16 characters.

The pattern ​

The choices here are not elements — they are cut positions.

Think of this like having a long chocolate bar made of several connected squares, and a knife. You can place your knife at any of the joints between the squares and make a cut. When you make a cut, you examine the piece you just broke off. If it's a valid palindrome, you put it in your pile and look at the remaining bar, deciding where to cut next. If the piece isn't a palindrome, you magically undo that cut and try cutting further down the bar instead.

Standing at index start, the piece you take next can end anywhere from start to the end of the string. Each ending is one branch. Take the piece only if it is a palindrome, recurse from just after it, then undo.

"aab", starting at 0:

  take "a"    → recurse from 1
      take "a"   → recurse from 2
          take "b" → recurse from 3 = end → record ["a","a","b"] ✓
      take "ab"  → not a palindrome, rejected
  take "aa"   → recurse from 2
      take "b"   → end → record ["aa","b"] ✓
  take "aab"  → not a palindrome, rejected

This is the same start-index loop as 4.18.1 Subsets. Only the meaning of the loop variable changed: it is a cut point rather than an item index.

Recognising that is the point of the problem. When you can phrase the choices as "what do I take next, and where does it end", the template is unchanged.

The solution ​

python
class Solution:
    def partition(self, s: str) -> List[List[str]]:
        result = []  # (1)
        path = []

        def is_palindrome(lo: int, hi: int) -> bool:  # (2)
            while lo < hi:
                if s[lo] != s[hi]:
                    return False
                lo += 1
                hi -= 1
            return True

        def backtrack(start: int):  # (3)
            if start == len(s):                     # (4) consumed the whole string
                result.append(path[:])
                return

            for end in range(start, len(s)):        # (5) the piece is s[start..end]
                if not is_palindrome(start, end):  # (6)
                    continue                        # prune: not a valid piece

                path.append(s[start:end + 1])  # (7)
                backtrack(end + 1)                  # (8) continue after this piece
                path.pop()  # (9)

        backtrack(0)
        return result
ts
function partition(s: string): string[][] {
  const result: string[][] = [];  // (1)
  const path: string[] = [];

  function isPal(lo: number, hi: number): boolean {  // (2)
    while (lo < hi) {
      if (s[lo] !== s[hi]) return false;
      lo++; hi--;
    }
    return true;
  }

  function backtrack(start: number): void {  // (3)
    if (start === s.length) {  // (4)
      result.push([...path]);
      return;
    }
    for (let end = start; end < s.length; end++) {  // (5)
      if (!isPal(start, end)) continue;  // (6)

      path.push(s.slice(start, end + 1));  // (7)
      backtrack(end + 1);  // (8)
      path.pop();  // (9)
    }
  }

  backtrack(0);
  return result;
}

Line by line ​

(1) result collects every way of cutting the string, and path holds the pieces chosen so far.

(2) Is s[lo..hi] a palindrome? Two pointers move inward from both ends, as in 4.5.1. It works on positions, so no new string is created.

(3) backtrack(start) cuts the rest of the string, from position start onward.

(4) The whole string has been cut into pieces. Save a copy of path.

(5) Try every possible next piece: from start to end, for each end.

(6) Only palindromes are allowed as pieces. This check runs before going deeper, so a bad piece ends that branch at once.

(7) Take the piece,

(8) cut the rest of the string, starting right after this piece, and

(9) undo, ready to try a longer piece.

The palindrome check is the pruning, and it happens before recursing. That is what stops the search exploring every one of the 2^{n-1} possible cuttings — most branches die at the check.

is_palindrome takes indices, not a substring. Passing s[start:end+1] would allocate a new string on every check, which is O(n) of pure waste per call. Comparing in place with two pointers is the same discipline as 4.2 and 4.5.1.

backtrack(end + 1) — the next piece starts immediately after the one just taken.

The base case is start == len(s), meaning the whole string has been consumed. There is no leftover to worry about, because every branch takes a piece and moves past it.

Edge cases ​

  • One character. One way to cut it: the single letter.
  • All the same letter, like "aaa". Every piece is a palindrome, so every possible cutting is valid: four of them.
  • No palindrome longer than one letter, like "abc". Only one cutting: every letter on its own.

Precomputing the palindromes ​

The palindrome check costs O(n) and is called from every node of the tree, and many of those checks repeat. You can compute all of them once, in O(n^2), with a small dynamic program:

python
n = len(s)
pal = [[False] * n for _ in range(n)]
for hi in range(n):
    for lo in range(hi, -1, -1):
        if s[lo] == s[hi] and (hi - lo < 2 or pal[lo + 1][hi - 1]):
            pal[lo][hi] = True

Read the condition: s[lo..hi] is a palindrome when its two ends match and the inside is already known to be one. hi - lo < 2 covers the pieces of length 1 and 2, which have no inside.

The loop order matters — lo counts downwards so that pal[lo+1][hi-1] is already filled when it is needed. That "fill the table in an order where the dependencies already exist" idea is the core of 4.24.

With the table, is_palindrome(lo, hi) becomes an O(1) lookup and the whole search drops a factor of n. Say this even if you do not write it — recognising the repeated work is the observation being tested.

Complexity ​

O(2^{n-1} \times n) in the worst case. A string of n characters has n−1 gaps and each is either cut or not, so there are 2^{n-1} possible partitions; copying each result costs O(n).

The worst case is a string like "aaaa", where every piece is a palindrome and nothing is ever pruned. On ordinary strings the pruning removes almost everything.

O(n) space for the recursion, or O(n^2) with the precomputed table.

Let's break this down:

  • Time Complexity: There are n-1 possible cut points in a string of length n. For each cut point, we either make a cut or we don't, giving 2^{n-1} possible partitions. For each valid partition, we slice and copy strings, taking O(n) time. The palindrome check itself takes O(n) string traversal, giving O(n \cdot 2^{n-1}) total worst-case time (like the string "aaaaa"). The DP precomputation reduces the inner check to O(1), but the copying still binds the overall worst case to O(n \cdot 2^{n-1}).
  • Space Complexity: The maximum depth of the recursion tree is n (if we cut every single character). The path array stores at most n items. If we use the DP table, it takes O(n^2) space. So O(n) or O(n^2) depending on the approach.

Where this goes next ​

  • Palindrome Partitioning II — the minimum number of cuts. Enumerating every partition and taking the smallest is far too slow. Because you only need an optimum rather than every answer, it becomes DP: O(n^2). 4.23.
  • Word Break II — cut a string into dictionary words and return all of them. Identical template with the dictionary check replacing the palindrome check.
  • Restore IP Addresses — cut a digit string into four valid octets. Same template, with a validity check and a piece-count limit.

The recurring dividing line: all the answers means backtracking; the best answer or how many means DP. Combination Sum II and Combination Sum IV sit on either side of it, and so do these two Palindrome Partitioning problems.

What the interviewer will push on ​

"What are the choices at each step?" Where the next piece ends.

"Where is the pruning?" The palindrome check before recursing.

"Why pass indices instead of substrings to the checker?" Slicing allocates and costs O(n) per check.

"Can you avoid re-checking the same substrings?" Precompute an n \times n table in O(n^2).

"What if you only needed the minimum number of cuts?" DP, not backtracking, and say why: you want one optimum, not every arrangement.

One thing to volunteer: point out that this is the subsets template where the loop variable is a cut position. Naming the reused skeleton is worth more than the code.

Next: 4.18.8 Letter Combinations of a Phone Number — the simplest possible branching, driven by a lookup table.

Combine chapters into one PDF

Pick the chapters you want. They print in the order you pick them.

Volume I — Technology
Part 0 — Retention & Notation
Part 1 — Foundations of Computation
Part 2 — Operating Systems
2.1 The Kernel
2.2 Processes
2.3 Threads & Scheduling
2.4 Concurrency Under the Hood
2.5 Memory Management
2.6 File Systems
2.7 Input/Output
2.8 Linux for Engineers
2.9 Windows & macOS in Practice
Part 3 — Languages, Compilers & Runtimes
3.6 JavaScript & V8
3.7 TypeScript
3.8 Node.js Internals
3.13 Python & CPython
3.14 FastAPI & Production Python
Part 4 — Data Structures & Algorithms
4.0 Classic Problems — Before NeetCode
4.4 Arrays & Hashing — Problems
4.5 Two Pointers
4.6 Sliding Window
4.8 Stack — Problems
4.9 Linked List — Problems
4.11 Binary Search — Problems
4.13 Trees
4.14 Tree — Problems
4.15 Trie — Problems
4.17 Heap — Problems
4.18 Backtracking — Problems
4.19 Graphs
4.20 Graph — Problems
4.21 Advanced Graph — Problems
4.23 1-D DP — Problems
4.24 2-D DP — Problems
4.26 Greedy — Problems
4.27 Interval — Problems
4.28 Math & Geometry — Problems
4.30 Bit Manipulation — Problems
Part 5 — Networking & the Web
5.3 IP
5.4 Transport
5.6 HTTP
Part 6 — Frontend Engineering
6.1 Browser Internals
6.2 HTML & CSS Mastery
6.3 JavaScript in the Browser
6.4 React, from First Component to Full Shop
6.5 Frameworks & Rendering
6.8 UI Engineering & Patterns
Part 7 — Databases & Storage
7.2 SQL Mastery
7.3 Storage Engine Internals
7.4 Transactions
7.5 NoSQL Taxonomy
7.8 Analytics & Big Data
Part 8 — Security, Identity & Cryptography
8.2 Cryptography
8.3 Protocols of Trust
8.4 Identity: AuthN & AuthZ
8.5 Application Security
8.6 Infrastructure Security
Part 9 — Software Design (LLD)
9.2 OOP Foundations
9.3 Design Principles
9.4 Design Patterns
9.5 Concurrency
9.6 API Design
9.7 LLD Interview Machines
9.9 Node/Express Production Playbook
Part 10 — Distributed Systems & HLD
10.7 Consistency & Consensus
10.8 Messaging & Microservices
10.14 Caching
Building blocks from the design seat
Part 11 — System Design Case Studies
Part 12 — AI & ML Engineering
12.1 What AI Engineering Is
12.2 The Math You Need
12.3 Classical Machine Learning
12.4 Data for ML
12.5 Deep Learning
12.6 Embeddings & Vector Search
12.7 Transformers & LLMs
12.8 Building with LLMs
12.9 Retrieval-Augmented Generation
12.10 Agents
12.11 Adapting Models
12.12 Production AI
12.13 Multimodal AI
12.14 AI Security & Governance
12.15 Case Studies & Capstone
Part 13 — Cloud, DevOps & Infrastructure
13.11 Git, from First Commit to Team Workflow
Part 14 — Containers: Docker & Kubernetes
14.1 Foundations
14.2 Docker
14.3 Kubernetes
14.4 Kubernetes on Azure
Part 15 — The Craft & Career
Nothing picked yet