Palindrome Partitioning II - Practice Coding Problems

Palindrome Partitioning II - Problem

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

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

A palindrome is a string that reads the same backward as forward.

Input & Output

Example 1 — Basic Partition

$ Input: s = "aab"

› Output: 1

💡 Note: The string can be partitioned as "aa|b". "aa" and "b" are both palindromes, requiring only 1 cut.

Example 2 — Already Palindrome

$ Input: s = "aba"

› Output: 0

💡 Note: The entire string "aba" is already a palindrome, so no cuts are needed.

Example 3 — Multiple Cuts Needed

$ Input: s = "abcde"

› Output: 4

💡 Note: Each character must be its own partition: "a|b|c|d|e", requiring 4 cuts.

Constraints

1 ≤ s.length ≤ 2000
s consists of lowercase English letters only

Visualization

Tap to expand

Understanding the Visualization

Input String

Given string that needs to be partitioned

Find Cuts

Determine optimal positions to make cuts

Verify Palindromes

Ensure each partition is a palindrome

Count Cuts

Return minimum number of cuts needed

Key Takeaway

🎯 Key Insight: Use DP to build minimum cuts incrementally, either with precomputed palindromes or expand-around-centers

Asked in

G Google 45 a Amazon 38 M Microsoft 32 f Facebook 28

The key insight is using dynamic programming to build up minimum cuts from smaller substrings. We can precompute palindromes or use expand-around-centers approach. Best approach is Optimized DP with Expand Around Centers for optimal space usage. Time: O(n²), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Optimized DP with Expand Around Centers	O(n²)	O(n)	Expand around centers to find palindromes while building DP solution
Recursion with Memoization	O(n³)	O(n²)	Cache results of recursive calls to avoid recomputation
1D Dynamic Programming	O(n²)	O(n²)	Build minimum cuts from bottom up with palindrome precomputation
Brute Force Recursion	O(2ⁿ)	O(n)	Try all possible partitions recursively

Optimized DP with Expand Around Centers — Algorithm Steps

Step 1: Initialize DP array with worst case
Step 2: Expand around each center
Step 3: Update minimum cuts for valid palindromes
Step 4: Return final result

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

DP array with worst case values

Expand

From each center, expand to find palindromes

Update

Update minimum cuts for each palindrome found

Result

Final DP value gives answer

Code -

solution.c — C

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

int solution(char* s) {
    int n = strlen(s);
    if (n <= 1) return 0;
    
    // DP array: dp[i] = minimum cuts for s[0:i+1]
    int dp[n];
    for (int i = 0; i < n; i++) {
        dp[i] = i;  // worst case: cut after each character
    }
    
    for (int center = 0; center < n; center++) {
        // Odd length palindromes
        int left = center, right = center;
        while (left >= 0 && right < n && s[left] == s[right]) {
            int cutsNeeded = left == 0 ? 0 : dp[left - 1] + 1;
            if (cutsNeeded < dp[right]) {
                dp[right] = cutsNeeded;
            }
            left--;
            right++;
        }
        
        // Even length palindromes
        left = center;
        right = center + 1;
        while (left >= 0 && right < n && s[left] == s[right]) {
            int cutsNeeded = left == 0 ? 0 : dp[left - 1] + 1;
            if (cutsNeeded < dp[right]) {
                dp[right] = cutsNeeded;
            }
            left--;
            right++;
        }
    }
    
    return dp[n - 1];
}

int main() {
    char s[2001];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    int result = solution(s);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

For each of n centers, we expand up to n/2 times on average

⚠ Quadratic Growth

Space Complexity

O(n)

Only DP array of size n, no palindrome table needed

⚡ Linearithmic Space

125.0K Views

Medium-High Frequency

~25 min Avg. Time

3.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Optimized DP with Expand Around Centers — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler