Palindrome Partitioning II | Front Partition

Welcome to Chapter 53 of the Dynamic Programming - DSA series. In this lesson, we explore Palindrome Partitioning II, mastering a distinct variant known as Front Partitioning (part of the partition DP family). We will systematically evolve from a naive recursive solution to an optimized memoized approach, and finally arrive at an efficient bottom-up tabulation strategy with $O(N^2)$ time complexity.

1. Why Do We Need This? (Problem Statement & Status Quo)

Given a string str, the objective is to partition the string such that every individual substring generated is a palindrome. Among all valid partitioning configurations, we must find the minimum number of cuts required.

The Naive Boundary Case

If you make a cut after every single character (i.e., $N - 1$ total cuts for a string of length $N$), every individual substring consists of a single character. Since every single character is inherently a palindrome, an answer always exists, and the maximum number of cuts required is at most $N - 1$.

However, the challenge is finding the minimum cuts.

2. Core Mental Model: Front Partitioning

Unlike Matrix Chain Multiplication (MCM) DP where we partition from an arbitrary pivot index $i$ to $j$ inside a range, Front Partitioning operates by anchoring at the front and scanning forward:

1. We start at the current index i (initially 0).
2. We iterate with a pointer J starting from i and moving forward to the end of the string.
3. At each step, the substring formed from index i to J (str[i...J]) is evaluated.
4. The Core Decision: If str[i...J] is a palindrome, we make a cut right after J, incur a cost of 1, and recursively solve the subproblem for the remaining string starting at J + 1.
5. We repeat this for all valid prefixes, taking the minimum cost among all possibilities.

3. Step-by-Step Evolution: The Recursive Blueprint

To construct any dynamic programming solution, we follow a rigorous 4-step framework:

1. Express everything in terms of index: We define a recursive function f(i) that returns the minimum cuts required to partition the suffix starting from index i into palindromic substrings.
2. Explore all possibilities: Iterate J from i to n - 1. Check if str[i...J] is a palindrome.
3. Take the minimum: If it is a palindrome, the cost is 1 + f(J + 1). We take the minimum cost across all valid J choices.
4. Base Case: When index i reaches the end of the string (i == n), no more cuts are needed, so we return 0.

Initial Recursive Implementation

int solve(int i, int n, string &str) {
    // Base Case: Reached the end of the string
    if (i == n) return 0;
    
    int minCost = INT_MAX;
    
    // Try all possible partitions from i to n-1
    for (int j = i; j < n; j++) {
        // Check if the prefix from i to j is a palindrome
        if (isPalindrome(i, j, str)) {
            int cost = 1 + solve(j + 1, n, str);
            minCost = min(minCost, cost);
        }
    }
    return minCost;
}

Note on Final Output Adjustment: Depending on how recursion handles terminal partitions, calling solve(0) on certain structures might count an extra trailing partition at the absolute end. As demonstrated in the lecture, the raw recursive/memoized result may require a -1 adjustment at the root call (or careful handling of boundary conditions) to yield the exact minimum cuts. In our optimized formulations below, we handle state transitions cleanly.

4. Adding Memoization (Top-Down DP)

The recursive approach evaluates overlapping subproblems repeatedly, leading to exponential time complexity. Since the only changing parameter in our state is the index i (ranging from 0 to n), we can cache results in a 1D DP array of size N.

Memoized Code Implementation

#include <bits/stdc++.h>
using namespace std;

class Solution {
private:
    bool isPalindrome(int i, int j, string &s) {
        while (i < j) {
            if (s[i] != s[j]) return false;
            i++;
            j--;
        }
        return true;
    }

    int memoize(int i, int n, string &str, vector<int> &dp) {
        // Base Case
        if (i == n) return 0;
        
        // Return cached result if available
        if (dp[i] != -1) return dp[i];
        
        int minCost = INT_MAX;
        
        for (int j = i; j < n; j++) {
            if (isPalindrome(i, j, str)) {
                int cost = 1 + memoize(j + 1, n, str, dp);
                minCost = min(minCost, cost);
            }
        }
        return dp[i] = minCost;
    }

public:
    int minCut(string s) {
        int n = s.size();
        vector<int> dp(n, -1);
        // Subtract 1 because the partition at the very end 
        // counts an extra cut in this front-partition structure.
        return memoize(0, n, s, dp) - 1;
    }
};

5. Converting to Bottom-Up Tabulation (Iterative DP)

To eliminate auxiliary stack space overhead, we convert the top-down memoization approach into a bottom-up tabulation method.

Tabulation Strategy

• Base Case: In memoization, i == n returned 0. Therefore, in our DP table, dp[n] = 0.
• Loop Direction: Since recursion goes from 0 to n, tabulation loops backward from n - 1 down to 0.
• DP Table Definition: dp[i] represents the minimum cuts required for the substring starting at index i.

Bottom-Up Code Implementation

#include <bits/stdc++.h>
using namespace std;

class Solution {
private:
    bool isPalindrome(int i, int j, string &s) {
        while (i < j) {
            if (s[i] != s[j]) return false;
            i++;
            j--;
        }
        return true;
    }

public:
    int minCut(string s) {
        int n = s.size();
        // Allocate size n + 1 to safely access dp[j + 1] when j reaches n - 1
        vector<int> dp(n + 1, 0);
        
        // Base case: dp[n] = 0 (already initialized by vector)

        // Fill table from n-1 down to 0
        for (int i = n - 1; i >= 0; i--) {
            int minCost = INT_MAX;
            for (int j = i; j < n; j++) {
                if (isPalindrome(i, j, s)) {
                    int cost = 1 + dp[j + 1];
                    minCost = min(minCost, cost);
                }
            }
            dp[i] = minCost;
        }
        
        // Return result for index 0, adjusted by -1 for the final boundary cut
        return dp[0] - 1;
    }
};

6. Complexity Analysis

Note on Optimization: *While the nested loops and palindrome check technically contribute an $O(n^3)$ worst-case time complexity, the constraints on typical interview problems (e.g., $N \le 2000$) pass comfortably within time limits. In advanced solutions, the palindrome check can be precomputed in $O(n^2)$ using a 2D boolean DP table, reducing overall time complexity to strict $O(n^2)$.

7. Summary and Key Takeaways

• Problem Category: Palindrome Partitioning II falls under Partition DP, specifically utilizing a Front Partitioning strategy.
• Front Partitioning Mechanics: Anchor at index i, scan forward with pointer J, and evaluate prefixes str[i...J].
• State Definition: A single parameter i representing the starting index of the remaining unpartitioned suffix.
• Transition Logic: If str[i...J] is a palindrome, the recurrence relation is 1 + f(J + 1). We take the minimum across all valid J.
• Base Case Handling: When index i reaches n, return 0.
• Space Optimization: Moving from recursion to tabulation removes auxiliary stack space, leaving only the $O(n)$ space required for the 1D DP table.
• Final Result Correction: Account for the terminal partition offset by subtracting 1 from dp[0] in the final return statement.