Palindrome Partitioning

Given a string, a partitioning of the string is a palindrome partitioning if every substring of the partition is a palindrome. Find the minimum cuts needed for a palindrome partitioning of a given string.

Examples

Example 1

Input String: "ababbbabbababa"
Output: 3
Explanation: The minimum cuts needed is 3: "a | babbbab | b | ababa".

Example 2

Input String: "geek"
Output: 2
Explanation: The minimum cuts needed is 2: "g | ee | k".

Example 3

Input String: "aaaa"
Output: 0
Explanation: The entire string is a palindrome; no cuts are required.

Standard Recurrence - O(N^3)

Let minCuts(i, j) be the minimum cuts needed to partition substring str[i..j] such that all sub-parts are palindromes.

If str[i..j] is a palindrome: minCuts(i, j) = 0
Otherwise, try all possible split points k between i and j - 1: minCuts(i, j) = min( 1 + minCuts(i, k) + minCuts(k+1, j) ) for all i <= k < j

1. Standard Tabulation - O(N^3) Time, O(N^2) Space

function isPalindrome(str, i, j) {
    while (i < j) {
        if (str[i] !== str[j]) return false;
        i++;
        j--;
    }
    return true;
}
 
function palindromePartitioningTab(str) {
    const n = str.length;
    // cuts[i][j] stores the min cuts needed for str[i..j]
    const cuts = Array.from({ length: n }, () => new Array(n).fill(0));
 
    // L is substring length
    for (let L = 2; L <= n; L++) {
        for (let i = 0; i < n - L + 1; i++) {
            let j = i + L - 1;
 
            // If substring is a palindrome, no cuts needed
            if (isPalindrome(str, i, j)) {
                cuts[i][j] = 0;
            } else {
                cuts[i][j] = Infinity;
                for (let k = i; k < j; k++) {
                    cuts[i][j] = Math.min(
                        cuts[i][j],
                        1 + cuts[i][k] + cuts[k + 1][j]
                    );
                }
            }
        }
    }
 
    return cuts[0][n - 1];
}

2. Optimized Tabulation - O(N^2) Time, O(N^2) Space

We can optimize the above solution by maintaining:

A 2D boolean table P[i][j] representing if str[i..j] is a palindrome.
A 1D array C[i] representing the minimum cuts needed for prefix str[0..i].

function palindromePartitioningOptimized(str) {
    const n = str.length;
    if (n <= 1) return 0;
 
    // P[i][j] will be true if substring str[i..j] is palindrome
    const P = Array.from({ length: n }, () => new Array(n).fill(false));
    // C[i] will store the min cuts needed for str[0..i]
    const C = new Array(n).fill(0);
 
    // Every substring of length 1 is a palindrome
    for (let i = 0; i < n; i++) {
        P[i][i] = true;
    }
 
    // Fill the palindrome lookup table P
    for (let L = 2; L <= n; L++) {
        for (let i = 0; i < n - L + 1; i++) {
            let j = i + L - 1;
 
            if (L === 2) {
                P[i][j] = (str[i] === str[j]);
            } else {
                P[i][j] = (str[i] === str[j]) && P[i + 1][j - 1];
            }
        }
    }
 
    // Calculate minimum cuts
    for (let i = 0; i < n; i++) {
        if (P[0][i] === true) {
            C[i] = 0; // If str[0..i] is palindrome, 0 cuts needed
        } else {
            C[i] = Infinity;
            for (let j = 0; j < i; j++) {
                if (P[j + 1][i] === true && 1 + C[j] < C[i]) {
                    C[i] = 1 + C[j];
                }
            }
        }
    }
 
    return C[n - 1];
}
 
// Driver code
const str = "ababbbabbababa";
console.log("Minimum cuts needed:", palindromePartitioningOptimized(str));
// Output: Minimum cuts needed: 3

Complexity Analysis

Time Complexity:
- Standard Tabulation: O(N^3)
- Optimized Tabulation: O(N^2)
Space Complexity: O(N^2)
- To store the 2D boolean palindrome lookup table of size N x N.

Matrix Chain Multiplication Allocate Minimum Pages