132. Palindrome Partitioning II - Solution

Q: Is Palindrome Partitioning II easy or hard?

Palindrome Partitioning II is classified as a Hard problem on LeetCode. The challenge comes from combining palindrome detection with dynamic programming to minimize cuts efficiently instead of checking all partitions.

Q: How to solve Palindrome Partitioning II in O(n^2)?

Use dynamic programming. Precompute palindrome substrings using a 2D DP table or detect them by expanding around centers. Maintain a DP array where dp[i] stores the minimum cuts for the prefix ending at index i, updating it whenever a palindrome substring is found.

Q: Palindrome Partitioning II Python or Java solution?

Both Python and Java implementations use the same DP logic. Maintain an array storing the minimum cuts for each prefix and either precompute palindrome substrings with a 2D table or detect them with center expansion. The overall complexity remains O(n^2).

Q: What is the best approach for Palindrome Partitioning II?

The most common solution uses dynamic programming with a palindrome table. First precompute whether every substring s[i..j] is a palindrome, then compute the minimum cuts needed for each prefix using DP. This approach runs in O(n^2) time and O(n^2) space and is the version most interviewers expect.

Q: What data structure is used in Palindrome Partitioning II?

The solution typically uses dynamic programming arrays and sometimes a 2D boolean table to store palindrome checks. Some optimized solutions replace the table with center expansion while keeping a DP array for minimum cuts.

Q: What is the time complexity of Palindrome Partitioning II?

Optimal solutions run in O(n^2) time. Both the palindrome-table dynamic programming approach and the center-expansion method examine O(n^2) substring combinations while updating minimum cut values.

Q: Is Palindrome Partitioning II asked at Google, Amazon, or Meta?

Palindrome Partitioning style problems appear frequently in interviews at companies like Amazon, Google, and Meta because they combine string manipulation with dynamic programming. Variants often test substring DP, palindrome detection, and optimal partitioning strategies.

The problem

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:

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

Example 2:

Input: s = "a"
Output: 0

Example 3:

Input: s = "ab"
Output: 1

Constraints:

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

Approach overview

Problem Overview: Given a string s, split it into substrings such that every substring is a palindrome. Return the minimum number of cuts required. A single character is already a palindrome, but longer segments must read the same forward and backward.

Approach 1: Dynamic Programming with Palindrome Table (Time: O(n^2), Space: O(n^2))

This method precomputes whether every substring s[i..j] is a palindrome. Use a 2D boolean table where pal[i][j] becomes true if the characters match and the inner substring s[i+1..j-1] is also a palindrome. Once this table is built, compute the minimum cuts using a DP array cuts[i] representing the minimum cuts needed for prefix s[0..i]. For each index, iterate backward to find valid palindrome segments and update cuts[i]. The precomputed palindrome table removes repeated checks, giving an overall O(n^2) time solution. This approach is common in dynamic programming problems involving substring partitions.

Approach 2: Center Expansion with Memoization (Time: O(n^2), Space: O(n))

Instead of storing all palindrome substrings, expand around each center to detect palindromes dynamically. For every index, expand for both odd and even length palindromes using two pointers moving outward. When a palindrome s[l..r] is found, update the minimum cuts needed for position r using previously computed results. A memoized DP array tracks the best cut count for every prefix of the string. This avoids the n × n palindrome table while still exploring all valid centers. The technique relies on the symmetry property of palindromes and is a common pattern in string problems involving substring checks.

Recommended for interviews: The dynamic programming approach with a palindrome table is the most expected answer. It clearly separates two ideas: detecting palindromes and minimizing cuts. Interviewers like this solution because the reasoning is easy to explain and guarantees O(n^2) time. The center expansion method is slightly more space efficient and demonstrates deeper understanding of palindrome properties, which can stand out in strong DP interviews.

Approach 1: Dynamic Programming with Palindrome Table

This approach involves using two DP tables. One to check if a substring is a palindrome and another to compute the minimum cuts required.

We maintain a 2D boolean table where palindrome[i][j] is true if the substring s[i...j] is a palindrome. Using this table, we calculate the minimum number of palindrome partitions.

Python

def minCut(s: str) -> int:
    n = len(s)
    palindrome = [[False] * n for _ in range(n)]
    cuts = [0] * n

    for i in range(n):
        min_cut = i
        for j in range(i + 1):
            if s[j] == s[i] and (i - j <= 2 or palindrome[j + 1][i - 1]):
                palindrome[j][i] = True
                min_cut = 0 if j == 0 else min(min_cut, cuts[j - 1] + 1)

        cuts[i] = min_cut

    return cuts[n - 1]

# Example usage:
s = "aab"
print(f"Minimum cuts needed for Palindrome Partitioning: {minCut(s)}")

Java

class Solution {
    public int minCut(String s) {
        int n = s.length();
        boolean[][] palindrome = new boolean[n][n];
        int[] cuts = new int[n];

        for (int i = 0; i < n; i++) {
            int minCut = i;
            for (int j = 0; j <= i; j++) {
                if (s.charAt(j) == s.charAt(i) && (i - j <= 2 || palindrome[j + 1][i - 1])) {
                    palindrome[j][i] = true;
                    minCut = j == 0 ? 0 : Math.min(minCut, cuts[j - 1] + 1);
                }
            }
            cuts[i] = minCut;
        }

        return cuts[n - 1];
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        String s = "aab";
        System.out.println("Minimum cuts needed for Palindrome Partitioning: " + sol.minCut(s));
    }
}

C++

#include <vector>
#include <string>
#include <iostream>
using namespace std;

int minCut(string s) {
    int n = s.size();
    vector<vector<bool>> palindrome(n, vector<bool>(n, false));
    vector<int> cuts(n, 0);

    for (int i = 0; i < n; ++i) {
        int min_cut = i;
        for (int j = 0; j <= i; ++j) {
            if (s[j] == s[i] && (i - j <= 2 || palindrome[j + 1][i - 1])) {
                palindrome[j][i] = true;
                min_cut = j == 0 ? 0 : min(min_cut, cuts[j - 1] + 1);
            }
        }
        cuts[i] = min_cut;
    }

    return cuts[n - 1];
}

int main() {
    string s = "aab";
    cout << "Minimum cuts needed for Palindrome Partitioning: " << minCut(s) << endl;
    return 0;
}

JavaScript

var minCut = function(s) {
    const n = s.length;
    const palindrome = Array.from({ length: n }, () => Array(n).fill(false));
    const cuts = Array(n).fill(0);

    for (let i = 0; i < n; i++) {
        let minCut = i;
        for (let j = 0; j <= i; j++) {
            if (s[j] == s[i] && (i - j <= 2 || palindrome[j + 1][i - 1])) {
                palindrome[j][i] = true;
                minCut = j == 0 ? 0 : Math.min(minCut, cuts[j - 1] + 1);
            }
        }
        cuts[i] = minCut;
    }

    return cuts[n - 1];
};

console.log("Minimum cuts needed for Palindrome Partitioning: " + minCut("aab"));

#include <stdbool.h>
#include <stdio.h>
#include <string.h>

int minCut(char *s) {
    int n = strlen(s);
    bool palindrome[n][n];
    int cuts[n];

    for (int i = 0; i < n; i++) {
        cuts[i] = i; 
        for (int j = 0; j <= i; j++) {
            if (s[j] == s[i] && (i - j <= 2 || palindrome[j + 1][i - 1])) {
                palindrome[j][i] = true;
                cuts[i] = j == 0 ? 0 : (cuts[j - 1] + 1);
            }
        }
    }

    return cuts[n - 1];
}

int main() {
    char s[] = "aab";
    printf("Minimum cuts needed for Palindrome Partitioning: %d\n", minCut(s));
    return 0;
}

using System;

public class Solution {
    public int MinCut(string s) {
        int n = s.Length;
        bool[,] palindrome = new bool[n, n];
        int[] cuts = new int[n];

        for (int i = 0; i < n; i++) {
            int minCut = i; 
            for (int j = 0; j <= i; j++) {
                if (s[j] == s[i] && (i - j <= 2 || palindrome[j + 1, i - 1])) {
                    palindrome[j, i] = true;
                    minCut = j == 0 ? 0 : Math.Min(minCut, cuts[j - 1] + 1);
                }
            }
            cuts[i] = minCut;
        }

        return cuts[n - 1];
    }

    public static void Main(string[] args) {
        Solution solution = new Solution();
        Console.WriteLine("Minimum cuts needed for Palindrome Partitioning: " + solution.MinCut("aab"));
    }
}

In Python, the implementation leverages list comprehension to initialize the palindrome table. The nested loops iterate through the string and update the palindrome conditions and cuts in a similar manner to other languages.

Complexity

Time Complexity: O(n^2) because every potential substring is evaluated.
Space Complexity: O(n^2), considering the 2D table to store palindromic checks.

Try this approach in the editor

Approach 2: Center Expansion with Memoization

This approach utilizes the idea of expanding around potential palindrome centers, combined with a memoization strategy to store minimum cuts. It significantly reduces redundant calculations by only considering centers and keeping track of the best solutions observed so far.

Python

def minCut(s: str) -> int:
    def extendPalindrome(s, start, end, dp):
        while start >= 0 and end < len(s) and s[start] == s[end]:
            dp[end] = min(dp[end], 0 if start == 0 else dp[start-1] + 1)
            start -= 1
            end += 1

    n = len(s)
    dp = list(range(n))
    for center in range(n):
        extendPalindrome(s, center, center, dp)
        extendPalindrome(s, center, center + 1, dp)
    return dp[n-1]

# Example usage:
s = "aab"
print(f"Minimum cuts using center expansion: {minCut(s)}")

Java

class Solution {
    private void extendPalindrome(String s, int start, int end, int[] dp) {
        while (start >= 0 && end < s.length() && s.charAt(start) == s.charAt(end)) {
            dp[end] = Math.min(dp[end], start == 0 ? 0 : dp[start - 1] + 1);
            start--;
            end++;
        }
    }

    public int minCut(String s) {
        int n = s.length();
        int[] dp = new int[n];
        for (int i = 0; i < n; i++) dp[i] = i;
        for (int center = 0; center < n; center++) {
            extendPalindrome(s, center, center, dp);
            extendPalindrome(s, center, center + 1, dp);
        }
        return dp[n - 1];
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println("Minimum cuts using center expansion: " + solution.minCut("aab"));
    }
}

C++

#include <iostream>
#include <vector>
#include <string>
#include <climits>
using namespace std;

void extendPalindromeAndCalculateCuts(const string &s, int start, int end, vector<int> &dp) {
    while (start >= 0 && end < s.size() && s[start] == s[end]) {
        dp[end] = min(dp[end], (start == 0 ? 0 : dp[start - 1] + 1));
        start--;
        end++;
    }
}

int minCut(string s) {
    int n = s.size();
    vector<int> dp(n);
    for (int i = 0; i < n; i++) dp[i] = i;
    for (int center = 0; center < n; center++) {
        extendPalindromeAndCalculateCuts(s, center, center, dp);
        extendPalindromeAndCalculateCuts(s, center, center + 1, dp);
    }
    return dp[n-1];
}

int main() {
    string s = "aab";
    cout << "Minimum cuts using center expansion: " << minCut(s) << endl;
    return 0;
}

JavaScript

var minCut = function(s) {
    const extendPalindrome = function(s, start, end, dp) {
        while (start >= 0 && end < s.length && s[start] === s[end]) {
            dp[end] = Math.min(dp[end], start === 0 ? 0 : dp[start - 1] + 1);
            start--;
            end++;
        }
    };

    const n = s.length;
    const dp = Array.from({length: n}, (_, i) => i);

    for (let center = 0; center < n; center++) {
        extendPalindrome(s, center, center, dp);
        extendPalindrome(s, center, center + 1, dp);
    }

    return dp[n - 1];
};

console.log("Minimum cuts using center expansion: " + minCut("aab"));

#include <stdio.h>
#include <string.h>
#include <limits.h>

int extendPalindromeAndCalculateCuts(const char *s, int start, int end, int *dp) {
    while (start >= 0 && end < strlen(s) && s[start] == s[end]) {
        dp[end] = (start == 0) ? 0 : ((dp[end] < dp[start - 1] + 1) ? dp[end] : dp[start - 1] + 1);
        start--;
        end++;
    }
    return dp[end-1];
}

int minCut(char *s) {
    int n = strlen(s);
    int dp[n];
    for (int i = 0; i < n; i++) dp[i] = i;
    for (int center = 0; center < n; center++) {
        extendPalindromeAndCalculateCuts(s, center, center, dp);
        extendPalindromeAndCalculateCuts(s, center, center + 1, dp);
    }
    return dp[n-1];
}

int main() {
    char s[] = "aab";
    printf("Minimum cuts using center expansion: %d\n", minCut(s));
    return 0;
}

using System;

public class Solution {
    private void ExtendPalindrome(string s, int start, int end, int[] dp) {
        while (start >= 0 && end < s.Length && s[start] == s[end]) {
            dp[end] = Math.Min(dp[end], start == 0 ? 0 : dp[start - 1] + 1);
            start--;
            end++;
        }
    }

    public int MinCut(string s) {
        int n = s.Length;
        int[] dp = new int[n];
        for (int i = 0; i < n; i++) dp[i] = i;
        for (int center = 0; center < n; center++) {
            ExtendPalindrome(s, center, center, dp);
            ExtendPalindrome(s, center, center + 1, dp);
        }
        return dp[n - 1];
    }

    public static void Main(string[] args) {
        Solution solution = new Solution();
        Console.WriteLine("Minimum cuts using center expansion: " + solution.MinCut("aab"));
    }
}

Python implementation embraces center expansion combined with a dynamic programming array to track minimal cuts, aiming to tighten the calculation around palindrome potentials.

Complexity

Time Complexity: O(n^2), viewing each character expansion.
Space Complexity: O(n), with space reserved for a single array.

Try this approach in the editor

Approach 3: Dynamic Programming

First, we preprocess the string s to determine whether each substring s[i..j] is a palindrome, and record this in a 2D array g[i][j], where g[i][j] indicates whether the substring s[i..j] is a palindrome.

Next, we define f[i] to represent the minimum number of cuts needed for the substring s[0..i-1]. Initially, f[i] = i.

Next, we consider how to transition the state for f[i]. We can enumerate the previous cut point j. If the substring s[j..i] is a palindrome, then f[i] can be transitioned from f[j]. If j = 0, it means that s[0..i] itself is a palindrome, and no cuts are needed, i.e., f[i] = 0. Therefore, the state transition equation is as follows:

$f[i] = min_{0 leq j leq i} \begin{cases} f[j-1] + 1, & if\ g[j][i] = True \ 0, & if\ g[0][i] = True \end{cases}

The answer is f[n], where n is the length of the string s.

The time complexity is O(n^2), and the space complexity is O(n^2). Here, n is the length of the string s$.

TypeScript

function minCut(s: string): number {
    const n = s.length;
    const g: boolean[][] = Array.from({ length: n }, () => Array(n).fill(true));
    for (let i = n - 1; ~i; --i) {
        for (let j = i + 1; j < n; ++j) {
            g[i][j] = s[i] === s[j] && g[i + 1][j - 1];
        }
    }
    const f: number[] = Array.from({ length: n }, (_, i) => i);
    for (let i = 1; i < n; ++i) {
        for (let j = 0; j <= i; ++j) {
            if (g[j][i]) {
                f[i] = Math.min(f[i], j ? 1 + f[j - 1] : 0);
            }
        }
    }
    return f[n - 1];
}

func minCut(s string) int {
	n := len(s)
	g := make([][]bool, n)
	f := make([]int, n)
	for i := range g {
		g[i] = make([]bool, n)
		f[i] = i
		for j := range g[i] {
			g[i][j] = true
		}
	}
	for i := n - 1; i >= 0; i-- {
		for j := i + 1; j < n; j++ {
			g[i][j] = s[i] == s[j] && g[i+1][j-1]
		}
	}
	for i := 1; i < n; i++ {
		for j := 0; j <= i; j++ {
			if g[j][i] {
				if j == 0 {
					f[i] = 0
				} else {
					f[i] = min(f[i], f[j-1]+1)
				}
			}
		}
	}
	return f[n-1]
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Dynamic Programming with Palindrome Table	Time Complexity: O(n^2) because every potential substring is evaluated. Space Complexity: O(n^2), considering the 2D table to store palindromic checks.
Center Expansion with Memoization	Time Complexity: O(n^2), viewing each character expansion. Space Complexity: O(n), with space reserved for a single array.
Dynamic Programming	–

Complexity analysis

Approach	Time	Space	When to Use
Dynamic Programming with Palindrome Table	O(n^2)	O(n^2)	Standard interview solution when clarity is more important than memory usage
Center Expansion with Memoization	O(n^2)	O(n)	When you want to avoid storing the full palindrome table and compute palindromes on the fly

Frequently asked questions

Is Palindrome Partitioning II easy or hard?

Palindrome Partitioning II is classified as a Hard problem on LeetCode. The challenge comes from combining palindrome detection with dynamic programming to minimize cuts efficiently instead of checking all partitions.

How to solve Palindrome Partitioning II in O(n^2)?

Use dynamic programming. Precompute palindrome substrings using a 2D DP table or detect them by expanding around centers. Maintain a DP array where dp[i] stores the minimum cuts for the prefix ending at index i, updating it whenever a palindrome substring is found.

Palindrome Partitioning II Python or Java solution?

Both Python and Java implementations use the same DP logic. Maintain an array storing the minimum cuts for each prefix and either precompute palindrome substrings with a 2D table or detect them with center expansion. The overall complexity remains O(n^2).

What is the best approach for Palindrome Partitioning II?

The most common solution uses dynamic programming with a palindrome table. First precompute whether every substring s[i..j] is a palindrome, then compute the minimum cuts needed for each prefix using DP. This approach runs in O(n^2) time and O(n^2) space and is the version most interviewers expect.

What data structure is used in Palindrome Partitioning II?

The solution typically uses dynamic programming arrays and sometimes a 2D boolean table to store palindrome checks. Some optimized solutions replace the table with center expansion while keeping a DP array for minimum cuts.

What is the time complexity of Palindrome Partitioning II?

Optimal solutions run in O(n^2) time. Both the palindrome-table dynamic programming approach and the center-expansion method examine O(n^2) substring combinations while updating minimum cut values.

Is Palindrome Partitioning II asked at Google, Amazon, or Meta?

Palindrome Partitioning style problems appear frequently in interviews at companies like Amazon, Google, and Meta because they combine string manipulation with dynamic programming. Variants often test substring DP, palindrome detection, and optimal partitioning strategies.

Palindrome Partitioning II solution and explanation

The problem

Approach overview

Approach 1: Dynamic Programming with Palindrome Table

Approach 2: Center Expansion with Memoization

Approach 3: Dynamic Programming

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Palindrome Partitioning II solution and explanation

The problem

Approach overview

Approach 1: Dynamic Programming with Palindrome Table

Approach 2: Center Expansion with Memoization

Approach 3: Dynamic Programming

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems