What is the brute force approach and complexity for Palindrome Partitioning II?

Try each palindrome that starts at i, then split the rest the same way with time complexity O(N^2 · 2^N) and space complexity O(N).

What is the optimal approach and complexity for Palindrome Partitioning II?

Grow each palindrome from its centre; s[l..r] lowers cuts[r] to cuts[l−1] + 1 with optimal time complexity O(N^2) and space complexity O(N).

Palindrome Partitioning II

Q: How do you identify the pattern for Palindrome Partitioning II?

Look for key signals in the prompt: "fewest cuts so every piece is a palindrome" indicates A minimum over ways to split. Each piece is a palindrome range, so the table is over ranges.; "every piece is a palindrome" indicates Each piece must pass the palindrome rule. Once it passes, the cut counts for the prefix before it can be reused.; "return the minimum cuts (0 when already a palindrome)" indicates The answer for a whole palindrome is 0. The base value for every prefix is 0 when it is a palindrome..

Hard·LeetCode #132 Pro OnlyTricky / Edge Case

LeetCode

Problem Statement

You are given a string s. Cut it into pieces so that every piece is a palindrome. Return the fewest cuts you need to do this. If the whole string is already a palindrome, the answer is 0.

Input

A string s of lowercase letters.

Output

The fewest cuts that split s into palindromes.

Example 1

Input: s = "aab"

Output: 1

One cut gives aa and b, and both are palindromes.

Example 2

Input: s = "a"

Output: 0

The string is already a palindrome, so no cut is needed.

Example 3

Input: s = "ab"

Output: 1

Cut between a and b to get the two single letters.

Constraints

• 1 ≤ s.length ≤ 2000
• s consists of lowercase English letters only.

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“fewest cuts so every piece is a palindrome”

→ A minimum over ways to split. Each piece is a palindrome range, so the table is over ranges.

“every piece is a palindrome”

→ Each piece must pass the palindrome rule. Once it passes, the cut counts for the prefix before it can be reused.

“return the minimum cuts (0 when already a palindrome)”

→ The answer for a whole palindrome is 0. The base value for every prefix is 0 when it is a palindrome.

Approach Complexity Ladder

Brute Force — try every first pieceO(N^2 · 2^N)O(N)

Try each palindrome that starts at i, then split the rest the same way

Better — isPal table, then cuts for each prefixO(N^2)O(N^2)

Look up isPal[j][i] for each candidate piece; cuts[i] from the palindromes that end at i

Optimal — expand around every centre, update cutsO(N^2)O(N)

Grow each palindrome from its centre; s[l..r] lowers cuts[r] to cuts[l−1] + 1

Brute Force Intuition

Let pieces(i) be the fewest palindromes that split s[i..]. Every palindrome s[i..j] that starts at i is one choice. For each choice, the cost is 1 + pieces(j+1). Take the smallest. The answer is pieces(0) − 1 cuts.

Recognition rule for this sub-pattern:

dp[i][j] for the substring s[i..j]; expand from the centre or fill by increasing length.

Remember this · DP — Strings

Trigger

Longest common subsequence, edit distance, palindromes, matching with wildcards, interleaving.

Think

Look at the last characters: if they match, what do I do? If not, what are my options?

Key question

What does dp[i][j] mean, and what are the empty-string base cases?

Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms

Interactive step-by-step playback with pointer & array state transitions

52 comprehensive LLD chapters

Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions

40 C++ basics labs & hardware memory models

Vtables, byte layouts, assembly insights, and multi-threading race conditions

Production-ready C++23 source code

Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways

Create Free Account Log in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like DP — Strings translate into production architectures and low-level memory mechanics.

LLD Architecture