Palindrome Partitioning - O(n³) Timeout on 2000-Char Input
Input length 2000 triggered 5-minute timeout and 100% CPU due to naive O(n³) palindrome checking.
20+ years shipping performance-critical code where algorithms decide the bill. Written from production experience, not tutorials.
- ✓Deep production experience
- ✓Understanding of internals and trade-offs
- ✓Experience debugging complex systems
- Palindrome partitioning splits a string into substrings that are each palindromes.
- Two variants: find ALL such partitions (enumeration) or find MINIMUM cuts needed (optimisation).
- DP precomputes which substrings are palindromes in O(n²) time.
- Enumeration uses backtracking — exponential O(n·2ⁿ) — only feasible for n ≤ 20.
- Min cuts DP runs in O(n²) after palindrome table is built.
- Build the palindrome table once and reuse it for both variants — never compute substrings on the fly.
Palindrome Partitioning is a classic string problem where you must split a given string into substrings such that every substring is a palindrome. The core challenge isn't just finding any valid partition—it's often about finding the minimum number of cuts needed to achieve that, or enumerating all possible partitions.
This problem is a textbook trap for combinatorial explosion: a naive recursive approach that tries every possible cut point branches exponentially, yielding O(n·2ⁿ) time complexity, which becomes completely unusable beyond strings of length 20-30. The problem exists to teach you that not all recursive solutions are viable, and that recognizing overlapping subproblems is critical—it's a direct gateway to dynamic programming optimization.
In the ecosystem of string DP problems, Palindrome Partitioning sits alongside classics like Longest Palindromic Substring and Edit Distance. The key insight is that you can precompute a boolean table of all palindromic substrings in O(n²) time using center expansion or DP, then use a separate DP array to compute minimum cuts in O(n²).
The optimized bottom-up solution runs in O(n²) time and O(n²) space, handling 2000-character inputs comfortably. When you don't need minimum cuts but all partitions, you're stuck with backtracking and pruning—still exponential, but practical for strings up to ~15-20 characters.
Real-world applications are niche but concrete: DNA sequence analysis where palindromic motifs indicate regulatory regions, natural language processing for detecting palindromic phrases, and certain cryptography algorithms that rely on palindromic structures. However, for most production string processing, you'd reach for suffix arrays or Manacher's algorithm (O(n) for palindrome detection) rather than full partitioning.
The problem's real value is pedagogical—it forces you to confront combinatorial explosion head-on and internalize why DP matters. If you're hitting timeouts on 2000-character inputs, you've likely implemented the naive recursion or failed to precompute palindrome checks, and the fix is a textbook O(n²) DP refactor.
Imagine you have a string of letter-beads on a necklace: 'aabbc'. You want to snip the string into pieces so that every piece reads the same forwards and backwards — like 'aa', 'bb', 'c'. Palindrome Partitioning is just figuring out the smartest way to make those snips — either finding ALL possible ways to do it, or finding the FEWEST snips needed. Dynamic Programming is the trick that stops you from checking the same bead-runs over and over again.
Palindrome Partitioning shows up everywhere string processing gets serious — DNA sequence analysis, text compression, and a surprising number of competitive-programming finals. The naive approach of generating every possible split and checking each piece for palindrome-ness works on a 5-character string, but hand it a 1000-character string and you'll be waiting until retirement. The combinatorial explosion is real, and it bites hard if you haven't internalized why memoization changes everything here.
The problem has two distinct flavours that interview candidates routinely conflate. The first asks you to return every possible partition where each substring is a palindrome — essentially an enumeration problem. The second asks for the minimum number of cuts needed to make every partition piece a palindrome — an optimisation problem. Both use Dynamic Programming, but the DP tables, recurrences, and complexity profiles are completely different. Mixing them up mid-interview is a fast track to a rejection.
By the end of this article you'll have a crystal-clear mental model of both variants, working Java implementations you can actually run and tweak, a comparison of O(n³) vs O(n²) DP approaches for minimum cuts, and the exact edge-case reasoning interviewers probe for. You'll also understand why the palindrome pre-computation table is the unsung hero that unlocks the efficient solution.
Don't treat this as just theory — the failure patterns I cover are the ones that sank a real production text-segmentation service. Get the palindrome table wrong and you're looking at a 5-minute timeout for a 2000-character input.
Why Palindrome Partitioning Is a Combinatorial Explosion Trap
Palindrome partitioning is the problem of splitting a string into substrings such that every substring is a palindrome. The core mechanic: given a string s of length n, you must find all possible ways to cut it at positions 0..n-1 so that each resulting piece reads the same forwards and backwards. This is not a single partition — it's the set of all valid partitions, which grows exponentially with n.
In practice, the naive backtracking approach checks every possible cut point and validates each substring for palindrome property on the fly. For a 2000-character input, the number of partitions is astronomical — O(2^n) in the worst case — and even with memoization, the O(n³) DP solution (precomputing palindrome table + backtracking) will time out. The bottleneck is not the palindrome check but the sheer number of partitions you must enumerate.
This problem matters in real systems when you need to segment text for natural language processing, split sensitive data for tokenization, or decompose strings for parallel processing. If you treat it as a simple recursion exercise without understanding the combinatorial blowup, your service will hang or crash on moderately long inputs.
Minimum Cuts — Dynamic Programming O(n²)
The minimum cuts problem: find the smallest number of cuts such that every piece is a palindrome. This is pure DP, no recursion enumeration needed.
Define dp[i] = minimum cuts needed for prefix s[0..i]. The recurrence: dp[i] = min over j < i such that s[j+1..i] is palindrome of (dp[j] + 1)
We also need a boolean table isPal[i][j] indicating if s[i..j] is palindrome. Fill it bottom-up: isPal[i][j] = (s[i] == s[j]) && (j - i <= 2 || isPal[i+1][j-1])
Then for each i, we scan j from 0 to i: if isPal[j+1][i] true, we consider dp[j] + 1. If isPal[0][i] is true, dp[i] = 0.
The result is dp[n-1].
Here's the Java implementation. Notice we handle the base case explicitly: if the whole prefix is a palindrome, dp[i] = 0. That prevents the common bug where dp[0] ends up as 1 for 'a'.
One thing that catches people: dp[0] isn't always 0. If the first character alone is a palindrome (it always is), then dp[0] = 0. But the recurrence needs that base case explicitly. Forget it, and single-character strings return 1 cut instead of 0.
package io.thecodeforge; public class PalindromePartitioning { public static int minCut(String s) { int n = s.length(); boolean[][] isPal = new boolean[n][n]; // Precompute palindrome table for (int len = 1; len <= n; len++) { for (int i = 0; i + len - 1 < n; i++) { int j = i + len - 1; if (s.charAt(i) == s.charAt(j) && (len <= 2 || isPal[i+1][j-1])) { isPal[i][j] = true; } } } int[] dp = new int[n]; for (int i = 0; i < n; i++) { if (isPal[0][i]) { dp[i] = 0; } else { int min = Integer.MAX_VALUE; for (int j = 0; j < i; j++) { if (isPal[j+1][i]) { min = Math.min(min, dp[j] + 1); } } dp[i] = min; } } return dp[n-1]; } }
Start with the Naive Recursive Explosion — O(n·2ⁿ)
Don't jump to DP. First, understand why this problem eats naive recursion alive. The brute force tries every possible cut position, then recurses on both halves. Each subproblem itself branches into every possible subcut. You get a combinatorial detonation: O(n·2ⁿ) time complexity.
The check is simple enough — isPalindrome() runs in O(n) scanning from both ends. But the recursion tree doubles with each character. A 20-character string gives over a million partitions. Your production code dies on input longer than "hello".
Base case logic: single characters are trivially palindromes. If the entire substring is palindrome, cost is zero cuts. Otherwise, iterate cut positions from left+1 to right-1, compute left subproblem, right subproblem, add one for the cut itself, and track the minimum. This is exactly the matrix chain multiplication pattern — except instead of multiplication cost you're cutting strings.
This recursive approach has O(n) stack space. It's educational as a warm-up. Deploy it, and you'll see why we invented memoization.
// io.thecodeforge — dsa tutorial public class PalindromePartitionNaive { private static boolean isPalindrome(String s, int lo, int hi) { while (lo < hi) { if (s.charAt(lo) != s.charAt(hi)) return false; lo++; hi--; } return true; } public static int minCuts(String s, int start, int end) { if (start >= end || isPalindrome(s, start, end)) return 0; int best = Integer.MAX_VALUE; for (int cut = start; cut < end; cut++) { int left = minCuts(s, start, cut); int right = minCuts(s, cut + 1, end); best = Math.min(best, 1 + left + right); } return best; } public static void main(String[] args) { String input = "geek"; System.out.println("Minimum cuts: " + minCuts(input, 0, input.length() - 1)); } }
Optimized Bottom-Up DP — O(n²) Time, O(n²) Space
The production-grade solution. Two DP tables: one for palindrome checks, one for optimal cuts. Build the palindrome table first — it's cheaper than recomputing isPalindrome() every time. For a substring s[i..j], it's a palindrome iff s[i]==s[j] and either length≤3 or s[i+1..j-1] is palindrome. This lookup is O(1).
Now the cut DP: for each substring ending at index i, try every possible cut point j from 0 to i-1. If s[j+1..i] is palindrome, then cuts[i] = min(cuts[i], cuts[j] + 1). You're essentially asking: "What's the best cut to end at i?" Start with the worst case: cut after every character (cuts[i]=i). Then optimize.
Why does this work? It's the same recurrence as the recursive version but computed iteratively. The palindrome table turns an O(n) check into an O(1) lookup. Total time: O(n²) for palindrome table + O(n²) for cuts = O(n²).
This handles strings up to thousands of characters. No recursion depth issues. No memoization overhead. Just two triangular arrays and a nested loop. It's the solution that survives code review and production traffic.
// io.thecodeforge — dsa tutorial public class PalindromePartitionOFTWO { public static int minCuts(String s) { int n = s.length(); boolean[][] isPal = new boolean[n][n]; int[] cuts = new int[n]; for (int len = 1; len <= n; len++) { for (int i = 0; i + len - 1 < n; i++) { int j = i + len - 1; if (s.charAt(i) == s.charAt(j) && (len <= 3 || isPal[i + 1][j - 1])) isPal[i][j] = true; } } for (int i = 0; i < n; i++) { if (isPal[0][i]) { cuts[i] = 0; } else { cuts[i] = i; // worst case: cut at every position for (int j = 0; j < i; j++) { if (isPal[j + 1][i] && cuts[j] + 1 < cuts[i]) cuts[i] = cuts[j] + 1; } } } return cuts[n - 1]; } public static void main(String[] args) { System.out.println("geek: " + minCuts("geek")); System.out.println("ababbbabbababa: " + minCuts("ababbbabbababa")); } }
Practical Application — Beyond Interview Problems
Palindrome partitioning isn’t just a coding challenge; it solves real-world text processing and bioinformatics problems. In NLP, splitting text into palindromic segments is used for DNA sequence compression: palindromic subsequences in genomes (like restriction enzyme sites) suggest structural motifs. For example, CRISPR off‑target detection searches for palindromic repeats in sgRNA. In document storage, partitioning a string into palindromes reduces index size — each palindrome can be hashed once, and queries match against segments instead of whole documents. In chat applications, auto‑detecting palindromic phrases (like “racecar” or “A man, a plan, a canal — Panama”) enables funny filters or alert systems. The same DP core powers lexical analysis in compilers: recognizing palindromic tokens (e.g., “madam” in a DSL) can be done with the minimal‑cut algorithm, ensuring fast tokenization. Understanding this problem gives you transferable skills for string optimization tasks where you need to reduce redundancy or detect symmetry.
// io.thecodeforge — dsa tutorial // Real-world example: find min cuts for palindrome partitions public class PalindromeMinCuts { public int minCut(String s) { int n = s.length(); boolean[][] isPal = new boolean[n][n]; int[] dp = new int[n]; for (int i = 0; i < n; i++) { int min = i; for (int j = 0; j <= i; j++) { if (s.charAt(j) == s.charAt(i) && (i - j <= 2 || isPal[j+1][i-1])) { isPal[j][i] = true; min = (j == 0) ? 0 : Math.min(min, dp[j-1] + 1); } } dp[i] = min; } return dp[n-1]; } }
Solutions — From Recursive Explosion to DP Stability
The naive recursive solution tries every possible cut, leading to O(n·2ⁿ) time — fine for n=10, useless for n=100. The key insight is that many subproblems repeat: checking if substring s[i..j] is a palindrome is reused across cuts. The optimal solution uses central DP: precompute a boolean table isPal[i][j] in O(n²) via expanding centers, then compute minimal cuts with a 1D DP array. Progression: first, write the exponential recursion (understand the combinatorial trap). Second, memoize it for O(n³) — better but still heavy. Third, implement bottom-up DP: 1. Build isPal table using the recurrence: isPal[i][j] = (s[i] == s[j]) && (j-i <= 2 || isPal[i+1][j-1]). 2. Compute minCut[i] = min over j <= i of (j==0 ? 0 : minCut[j-1] + 1) if isPal[j][i]. Result: O(n²) time, O(n²) space. For memory-critical systems, you can compute cuts on-the-fly without full isPal table using two-pointer expansion per cut, trading time for space.
// io.thecodeforge — dsa tutorial // Optimal O(n²) solution with explicit palindrome table public class PalindromePartitionDP { public List<List<String>> partition(String s) { int n = s.length(); boolean[][] isPal = new boolean[n][n]; for (int i = n-1; i >= 0; i--) { for (int j = i; j < n; j++) { if (s.charAt(i) == s.charAt(j) && (j-i <= 2 || isPal[i+1][j-1])) { isPal[i][j] = true; } } } List<List<String>> result = new ArrayList<>(); backtrack(s, 0, new ArrayList<>(), result, isPal); return result; } private void backtrack(String s, int start, List<String> path, List<List<String>> result, boolean[][] isPal) { if (start == s.length()) { result.add(new ArrayList<>(path)); return; } for (int end = start; end < s.length(); end++) { if (isPal[start][end]) { path.add(s.substring(start, end+1)); backtrack(s, end+1, path, result, isPal); path.remove(path.size()-1); } } } }
Silent O(n³) Timeout on Input Length 2000
- Always precompute palindrome property into a DP table before running any partition algorithm.
- For min cuts, use O(n²) DP with the table; never scan substrings repeatedly.
- Benchmark with n=2000 before deploying — O(n³) is a silent killer.
- Also test with all-same characters to verify the enumeration path doesn't blow up.
jstack <pid> | grep -A 30 'partition'java -XX:+PrintGCDetails -jar app.jar 2>&1 | grep 'GC'java -Dtest.string='abba' -jar debug.jarecho 'Check isPalindrome[0][3] should be true'java -Xss2m -jar app.jarulimit -s unlimited (Linux only)| File | Command / Code | Purpose |
|---|---|---|
| io | public class PalindromePartitioning { | Minimum Cuts |
| PalindromePartitionNaive.java | public class PalindromePartitionNaive { | Start with the Naive Recursive Explosion |
| PalindromePartitionOFTWO.java | public class PalindromePartitionOFTWO { | Optimized Bottom-Up DP |
| PalindromeMinCuts.java | public class PalindromeMinCuts { | Practical Application |
| PalindromePartitionDP.java | public class PalindromePartitionDP { | Solutions |
Key takeaways
Common mistakes to avoid
4 patternsNot precomputing the palindrome table, checking isPalindrome() on the fly during DP.
Forgetting the base case dp[0] = 0 for single character.
Using recursion without memoization for minimum cuts.
Confusing the enumeration variant with the minimum cuts variant.
Practice These on LeetCode
Interview Questions on This Topic
Given a string s, return the minimum number of cuts needed to partition it into palindromic substrings.
Explain why the naive recursive approach for palindrome partitioning is exponential and how DP fixes it.
How would you modify the minimum cuts DP to also return one valid partition with that many cuts?
Frequently Asked Questions
O(n·2ⁿ) in the worst case. Each cut point branches into two subproblems, and checking palindrome takes O(n) per substring, leading to exponential blowup.
Use a boolean table isPal[i][j] where isPal[i][j] = (s[i] == s[j]) && (j - i <= 2 || isPal[i+1][j-1]). Fill it bottom-up by increasing substring length.
dp[i] = min over j < i where s[j+1..i] is palindrome of (dp[j] + 1). If s[0..i] is palindrome, dp[i] = 0. Result is dp[n-1].
The O(n³) solution recomputes palindrome checks for every substring during DP, resulting in ~8 billion operations. The O(n²) precomputation reduces this to ~4 million operations.
20+ years shipping performance-critical code where algorithms decide the bill. Written from production experience, not tutorials.
That's Dynamic Programming. Mark it forged?
5 min read · try the examples if you haven't