Log inSign up
hardleetcodeNot Started

Palindrome Partitioning II

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Strings
Solve on leetcode
Lesson

Problem Statement

Given a string s, partition s such that every substring of the partition is a palindrome.

Return the minimum cuts needed for a palindrome partitioning of s.

Example 1 · Example:

Input: s = "aab"
Output: 1
Explanation: The palindrome partitioning ["aa","b"] could be produced using 1 cut.

Example 2 · Example:

Input: s = "a"
Output: 0
Explanation: No cuts needed since "a" is already a palindrome.

Example 3 · Example:

Input: s = "ab"
Output: 1
Explanation: Partitioning ["a","b"] requires 1 cut.

Constraints:

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

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Formulate 1D partition DP state transitions.
  • Optimize palindrome lookups from O(N) to O(1).
  • Reduce memory footprint to O(N) via center expansion.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Finding minimum cuts/segments to partition a sequence into valid components.
  • Palindrome segmentation and grouping.

Algorithmic Decision Tree:

  • 1D Partition Dynamic Programming
  • Expand Around Center Transitions

Connected Patterns:

Palindrome PartitioningWord BreakLongest Palindromic Substring

1. Top-Down Recursion with Memoization

Intuition

Define minCuts(i) as the minimum cuts needed for suffix s[i...n-1]. If s[i...n-1] is a palindrome, return 0. Otherwise, for every j from i to n - 1, if s[i...j] is a palindrome, candidate cuts are 1 + minCuts(j + 1). Return the minimum across all valid j.

When to apply: Basic recursive formulation.

Algorithm

  1. Initialize memo array of size n with -1.
  2. Helper solve(i):
  3. If isPalindrome(s[i...n-1]): return 0.
  4. If memo[i] != -1: return memo[i].
  5. minCuts = Infinity.
  6. For j from i to n - 1:
  7. If isPalindrome(s[i...j]):
  8. minCuts = min(minCuts, 1 + solve(j + 1)).
  9. memo[i] = minCuts.
  10. Return minCuts.

Interactive Trace

2 of 2 questions left today
Step 1 / 5
Trace timeline20% explored
Current operationSTEP 1 OF 5
Initialize dp = [0, 1, 2]
Visual state
Values and pointers at this exact step
pointers
S
a
a
b
0
↑ i
1
2
Check / comparison
dp = [0, 1, 2]
Decision / next transition
Advance to next character/state.
Why this step matters

Initialize dp = [0, 1, 2].

Step 1 / 5
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <vector>
4#include <algorithm>
5
6class Solution {
7 bool isPalindrome(const std::string& s, int i, int j) {
8 while (i < j) {
9 if (s[i++] != s[j--]) return false;
10 }
11 return true;
12 }
13
14 int solve(int i, const std::string& s, std::vector<int>& memo) {
15 int n = s.size();
16 if (i >= n || isPalindrome(s, i, n - 1)) return 0;
17 if (memo[i] != -1) return memo[i];
18
19 int ans = n;
20 for (int j = i; j < n; ++j) {
21 if (isPalindrome(s, i, j)) {
22 ans = std::min(ans, 1 + solve(j + 1, s, memo));
23 }
24 }
25 return memo[i] = ans;
26 }
27public:
28 int minCut(std::string s) {
29 int n = s.size();
30 std::vector<int> memo(n, -1);
31 return solve(0, s, memo);
32 }
33};
34
35int main() {
36 Solution sol;
37 std::cout << sol.minCut("aab") << std::endl; // 1
38 std::cout << sol.minCut("a") << std::endl; // 0
39 return 0;
40}

Time & Space Complexity

  • Time complexity: O(N^3) — N states, each loop runs O(N) with O(N) palindrome check per iteration.
  • Space complexity: O(N)

Why Brute Force Doesn't Scale:

Combining center expansion with 1D DP achieves O(N2) time and O(N) space.

Only stores a single 1D array of integers.

2. 2D Palindrome Table + 1D DP

Intuition

Phase 1: Compute isPal[i][j] for all substrings using the recurrence isPal[i][j] = (s[i] == s[j] && (j - i < 2 || isPal[i+1][j-1])). Phase 2: Compute dp[i] (min cuts for s[0...i]). For each i, initialize dp[i] = i. For each j from 0 to i: if isPal[j][i] is true, dp[i] = (j == 0) ? 0 : min(dp[i], dp[j - 1] + 1). Return dp[n - 1].

When to apply: Standard structured dynamic programming approach.

Algorithm

  1. Precompute isPal[n][n] boolean matrix.
  2. Initialize dp[n] array with dp[i] = i (worst-case i cuts).
  3. For i from 0 to n - 1:
  4. For j from 0 to i:
  5. If isPal[j][i]:
  6. dp[i] = (j == 0) ? 0 : min(dp[i], dp[j - 1] + 1).
  7. Return dp[n - 1].

Interactive Trace

2 of 2 questions left today
Step 1 / 5
Trace timeline20% explored
Current operationSTEP 1 OF 5
Initialize dp = [0, 1, 2]
Visual state
Values and pointers at this exact step
pointers
S
a
a
b
0
↑ i
1
2
Check / comparison
dp = [0, 1, 2]
Decision / next transition
Advance to next character/state.
Why this step matters

Initialize dp = [0, 1, 2].

Step 1 / 5
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <vector>
4#include <algorithm>
5
6class Solution {
7public:
8 int minCut(std::string s) {
9 int n = s.size();
10 if (n <= 1) return 0;
11
12 std::vector<std::vector<bool>> isPal(n, std::vector<bool>(n, false));
13 for (int i = n - 1; i >= 0; --i) {
14 for (int j = i; j < n; ++j) {
15 if (s[i] == s[j] && (j - i < 2 || isPal[i + 1][j - 1])) {
16 isPal[i][j] = true;
17 }
18 }
19 }
20
21 std::vector<int> dp(n);
22 for (int i = 0; i < n; ++i) {
23 dp[i] = i; // Max cuts
24 for (int j = 0; j <= i; ++j) {
25 if (isPal[j][i]) {
26 dp[i] = (j == 0) ? 0 : std::min(dp[i], dp[j - 1] + 1);
27 }
28 }
29 }
30 return dp[n - 1];
31 }
32};
33
34int main() {
35 Solution sol;
36 std::cout << sol.minCut("aab") << std::endl; // 1
37 std::cout << sol.minCut("a") << std::endl; // 0
38 return 0;
39}

Time & Space Complexity

  • Time complexity: O(N^2) — Fills the N x N palindrome matrix and evaluates N2/2 DP transitions.
  • Space complexity: O(N^2) for isPal table

3. Center Expansion 1D DP (O(N) Space)

Intuition

Initialize dp[i] = i for all indices. For each center i, expand odd-length palindromes (i, i) and even-length palindromes (i, i + 1). For each matching boundary [left, right]: the palindrome spans from left to right. Update dp[right] = (left == 0) ? 0 : min(dp[right], dp[left - 1] + 1). Continue expanding until mismatch.

When to apply: Optimal benchmark solution for minimal memory footprint and high execution speed.

Algorithm

  1. Initialize dp of size n with dp[i] = i.
  2. Loop mid from 0 to n - 1:
  3. // Odd-length palindromes centered at mid
  4. Expand left = mid, right = mid: while valid and match:
  5. dp[right] = (left == 0) ? 0 : min(dp[right], dp[left - 1] + 1)
  6. left--, right++
  7. // Even-length palindromes centered between mid and mid + 1
  8. Expand left = mid, right = mid + 1: while valid and match:
  9. dp[right] = (left == 0) ? 0 : min(dp[right], dp[left - 1] + 1)
  10. left--, right++
  11. Return dp[n - 1].

Prefiltered Palindrome DP with 1D Minimal Cut Optimization

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [a, a, b]
Current operationSTEP 1 OF 6
Observation: Initialize dpCuts = [0, 1, 2]
Visual state
Values and pointers at this exact step
array
S
a
a
b
0
↑ dpCuts: [0, 1, 2]
1
2
Variables at this step
n
3
dpCuts
[0,1,2]
worstCase
Max cuts = index
Why this step matters

Observation: Initialize dpCuts = [0, 1, 2]. Worst case: each character in its own partition requires i cuts.

Decision: Use precomputed palindrome boolean table isPalin[j][i] to test if substring s[j..i] is a palindrome.

Invariant: dpCuts[i] represents minimal cuts needed for prefix s[0..i].

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <vector>
4#include <algorithm>
5
6class Solution {
7public:
8 int minCut(std::string s) {
9 int n = s.size();
10 if (n <= 1) return 0;
11
12 std::vector<int> dp(n);
13 for (int i = 0; i < n; ++i) dp[i] = i;
14
15 for (int mid = 0; mid < n; ++mid) {
16 // Odd length
17 for (int l = mid, r = mid; l >= 0 && r < n && s[l] == s[r]; --l, ++r) {
18 int newCut = (l == 0) ? 0 : dp[l - 1] + 1;
19 dp[r] = std::min(dp[r], newCut);
20 }
21 // Even length
22 for (int l = mid, r = mid + 1; l >= 0 && r < n && s[l] == s[r]; --l, ++r) {
23 int newCut = (l == 0) ? 0 : dp[l - 1] + 1;
24 dp[r] = std::min(dp[r], newCut);
25 }
26 }
27 return dp[n - 1];
28 }
29};
30
31int main() {
32 Solution sol;
33 std::cout << sol.minCut("aab") << std::endl; // 1
34 std::cout << sol.minCut("a") << std::endl; // 0
35 std::cout << sol.minCut("ab") << std::endl; // 1
36 return 0;
37}

Time & Space Complexity

  • Time complexity: O(N^2) — Expands from 2N - 1 centers updating a single 1D array of size N.
  • Space complexity: O(N) strictly

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Top-Down Recursion with MemoizationO(N^3)O(N^2)Natural translation of partition branching.High constant factor and potential recursion depth limits.
2.2D Palindrome Table + 1D DPO(N^2)O(N^2)Clean separation: phase 1 builds palindrome table, phase 2 computes cuts.Allocates an N x N boolean table.
3.Center Expansion 1D DP (Optimal)OptimalO(N^2)O(N) strictlyExpands around centers and updates 1D DP directly in O(N) space.Requires simultaneous odd/even center handling.

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Not handling l == 0 condition (which requires 0 cuts rather than dp[l - 1] + 1).

Pitfall 2:

Missing even-length palindrome centers.

Crucial Edge Cases to Validate:

  • Entire string is already a palindrome (e.g., racecar): When left expands to 0, dp[n - 1] is updated to 0 cuts.
  • All distinct characters (e.g., abcde): Requires n - 1 cuts, correctly returned as 4.
  • Single character string (s = a): Returns 0 cuts immediately.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Explain the 1D DP recurrence clearly: dp[i] depends on valid palindromic suffixes ending at i.
  2. Show the center expansion optimization to impress the interviewer with O(N) space efficiency.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why does expanding around centers save space compared to the 2D table DP approach?

Back to DSA Sheet