Palindrome Partitioning II (Min Cuts)

🎯

Palindrome Partitioning II (Min Cuts)

hardDPGoogleAmazon

Imagine you want to split a string into the fewest pieces possible so that each piece reads the same forwards and backwards, like cutting a necklace into palindromic beads.

💡 This problem is a classic example of dynamic programming on strings. Beginners often struggle because it combines palindrome checking with partitioning, requiring careful state definition and optimization to avoid exponential time.

📋

Problem Statement

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. Input: a string s. Output: an integer representing the minimum number of cuts needed.

1 ≤ s.length ≤ 10^5s consists of lowercase English letters only

💡

Example

Input"aab"

Output1

The palindrome partitioning ['aa','b'] could be produced using 1 cut.

Input"a"

Output0

The string itself is a palindrome, so no cuts are needed.

Input"abccba"

Output0

The entire string is a palindrome, so no cuts are needed.

• Single character string → 0 cuts
• String with all identical characters → 0 cuts
• String with no palindromic substrings longer than 1 → n-1 cuts
• Empty string (if allowed) → 0 cuts

🔁

Why DP?

Why greedy fails:

A greedy approach might try to cut at the first palindrome found, but this can lead to suboptimal partitions. For example, 'aab' greedy cutting after 'a' leads to more cuts than cutting after 'aa'.

DP state:

dp[i] represents the minimum number of cuts needed for the substring s[0..i].

Recurrence:dp[i] = min(dp[j] + 1) for all j < i where s[j+1..i] is palindrome

To find minimum cuts at i, try all partitions ending at i where the right part is palindrome, and pick the minimum cuts from left plus one cut.

⚠️

Common Mistakes

Not precomputing palindrome substrings

Repeated palindrome checks cause TLE

✅ Precompute palindrome table or use center expansion

Incorrect base case handling in recursion

Wrong minimum cuts or infinite recursion

✅ Return -1 or 0 correctly when substring end reached

Off-by-one errors in dp indexing

Index out of bounds or wrong results

✅ Carefully handle dp[j-1] and substring indices

Not initializing dp array with max cuts

Incorrect minimum cut calculations

✅ Initialize dp[i] = i as worst case

Updating dp array in wrong order in space optimized approach

Incorrect dp values due to overwritten states

✅ Use center expansion which naturally updates dp correctly

🧠

Brute Force (Pure Recursion with Palindrome Checks)

💡 This approach helps understand the problem's exponential nature and the need for optimization. It is the foundation for all DP solutions.

Intuition

Try every possible partition and check if the left substring is palindrome. If yes, recursively solve for the right substring and take the minimum cuts.

Algorithm

1. Check if the entire string is palindrome; if yes, return 0 cuts.
2. Otherwise, try cutting the string at every possible index.
3. For each cut, recursively compute minimum cuts for the right substring.
4. Return the minimum cuts found plus one for the current cut.

💡 The recursion tree grows exponentially because each cut leads to multiple recursive calls, making it inefficient.

Recurrence:minCuts(i) = 0 if s[i..end] is palindrome else min(1 + minCuts(j+1)) for i ≤ j < end if s[i..j] is palindrome

</>

Code

def minCut(s: str) -> int:
    def is_palindrome(sub: str) -> bool:
        return sub == sub[::-1]

    def dfs(start: int) -> int:
        if start == len(s):
            return -1  # no cut needed beyond end
        min_cuts = float('inf')
        for end in range(start, len(s)):
            if is_palindrome(s[start:end+1]):
                cuts = 1 + dfs(end + 1)
                if cuts < min_cuts:
                    min_cuts = cuts
        return min_cuts

    return dfs(0)

Line Notes

def is_palindrome(sub: str) -> bool:Helper to check palindrome, essential for correctness

if start == len(s):Base case: no more string left means no cuts needed

for end in range(start, len(s)):Try every possible cut end index

if is_palindrome(s[start:end+1]):Only proceed if left substring is palindrome

cuts = 1 + dfs(end + 1)Add one cut plus recursive cuts for right substring

return dfs(0)Start recursion from index 0

public class Solution {
    public int minCut(String s) {
        return dfs(s, 0);
    }

    private int dfs(String s, int start) {
        if (start == s.length()) return -1;
        int minCuts = Integer.MAX_VALUE;
        for (int end = start; end < s.length(); end++) {
            if (isPalindrome(s, start, end)) {
                int cuts = 1 + dfs(s, end + 1);
                if (cuts < minCuts) minCuts = cuts;
            }
        }
        return minCuts;
    }

    private boolean isPalindrome(String s, int left, int right) {
        while (left < right) {
            if (s.charAt(left++) != s.charAt(right--)) return false;
        }
        return true;
    }

    // public static void main(String[] args) {
    //     Solution sol = new Solution();
    //     System.out.println(sol.minCut("aab")); // 1
    // }
}

Line Notes

if (start == s.length()) return -1;Base case: no cuts needed beyond string end

for (int end = start; end < s.length(); end++) {Try all possible cut positions

if (isPalindrome(s, start, end)) {Check if left substring is palindrome

int cuts = 1 + dfs(s, end + 1);Add one cut plus recursive cuts for right substring

return minCuts;Return minimum cuts found

private boolean isPalindrome(String s, int left, int right)Efficient palindrome check helper

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

class Solution {
public:
    int minCut(string s) {
        return dfs(s, 0);
    }

private:
    int dfs(const string& s, int start) {
        if (start == s.size()) return -1;
        int minCuts = INT_MAX;
        for (int end = start; end < s.size(); ++end) {
            if (isPalindrome(s, start, end)) {
                int cuts = 1 + dfs(s, end + 1);
                if (cuts < minCuts) minCuts = cuts;
            }
        }
        return minCuts;
    }

    bool isPalindrome(const string& s, int left, int right) {
        while (left < right) {
            if (s[left++] != s[right--]) return false;
        }
        return true;
    }
};

// int main() {
//     Solution sol;
//     cout << sol.minCut("aab") << endl; // 1
//     return 0;
// }

Line Notes

if (start == s.size()) return -1;Base case: no cuts needed beyond string end

for (int end = start; end < s.size(); ++end) {Try all possible cut positions

if (isPalindrome(s, start, end)) {Check if left substring is palindrome

int cuts = 1 + dfs(s, end + 1);Add one cut plus recursive cuts for right substring

return minCuts;Return minimum cuts found

bool isPalindrome(const string& s, int left, int right)Helper to check palindrome efficiently

var minCut = function(s) {
    function isPalindrome(sub) {
        return sub === sub.split('').reverse().join('');
    }

    function dfs(start) {
        if (start === s.length) return -1;
        let minCuts = Infinity;
        for (let end = start; end < s.length; end++) {
            if (isPalindrome(s.substring(start, end + 1))) {
                let cuts = 1 + dfs(end + 1);
                if (cuts < minCuts) minCuts = cuts;
            }
        }
        return minCuts;
    }

    return dfs(0);
};

// console.log(minCut("aab")); // 1

Line Notes

function isPalindrome(sub) {Helper to check palindrome by reversing string

if (start === s.length) return -1;Base case: no cuts needed beyond string end

for (let end = start; end < s.length; end++) {Try all possible cut positions

if (isPalindrome(s.substring(start, end + 1))) {Check if left substring is palindrome

let cuts = 1 + dfs(end + 1);Add one cut plus recursive cuts for right substring

return dfs(0);Start recursion from index 0

⏱

Complexity

TimeO(2^n * n) due to palindrome checks and recursive calls

SpaceO(n) recursion stack depth

Each character can be a cut or not, leading to exponential partitions; palindrome checks add linear cost per call.

💡 For n=20, this means over a million recursive calls, which is impractical.

Interview Verdict: TLE

This approach is too slow for large inputs but is essential to understand the problem structure.

🧠

Memoization with Palindrome Preprocessing

💡 Memoization avoids recomputing subproblems by caching results, and precomputing palindrome substrings reduces repeated palindrome checks.

Intuition

Precompute a table to know if s[i..j] is palindrome in O(1). Use recursion with memo to store minimum cuts from index i onward.

Algorithm

1. Precompute a 2D boolean table for palindrome substrings.
2. Use recursion with memo to find minimum cuts from each index.
3. For each index, try all palindrome substrings starting there and recurse.
4. Return the cached minimum cuts to avoid recomputation.

💡 Memoization prunes the recursion tree drastically, and palindrome table makes palindrome checks O(1).

Recurrence:dp[i] = min(1 + dp[j+1]) for all j ≥ i where s[i..j] is palindrome

</>

Code

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

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

    memo = {}
    def dfs(start):
        if start == n:
            return -1
        if start in memo:
            return memo[start]
        min_cuts = float('inf')
        for end in range(start, n):
            if palindrome[start][end]:
                cuts = 1 + dfs(end + 1)
                if cuts < min_cuts:
                    min_cuts = cuts
        memo[start] = min_cuts
        return min_cuts

    return dfs(0)

Line Notes

palindrome = [[False]*n for _ in range(n)]Initialize 2D table to store palindrome info

for i in range(n-1, -1, -1):Fill palindrome table bottom-up to use smaller substrings

if s[i] == s[j] and (j - i < 2 or palindrome[i+1][j-1])Check palindrome condition using smaller substring

memo = {}Memo dictionary to cache minimum cuts from each start index

if start in memo:Return cached result to avoid recomputation

for end in range(start, n):Try all palindrome substrings starting at start

memo[start] = min_cutsCache computed minimum cuts

public class Solution {
    public int minCut(String s) {
        int n = s.length();
        boolean[][] palindrome = 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 || palindrome[i + 1][j - 1])) {
                    palindrome[i][j] = true;
                }
            }
        }
        Integer[] memo = new Integer[n];
        return dfs(s, 0, palindrome, memo);
    }

    private int dfs(String s, int start, boolean[][] palindrome, Integer[] memo) {
        if (start == s.length()) return -1;
        if (memo[start] != null) return memo[start];
        int minCuts = Integer.MAX_VALUE;
        for (int end = start; end < s.length(); end++) {
            if (palindrome[start][end]) {
                int cuts = 1 + dfs(s, end + 1, palindrome, memo);
                if (cuts < minCuts) minCuts = cuts;
            }
        }
        memo[start] = minCuts;
        return minCuts;
    }

    // public static void main(String[] args) {
    //     Solution sol = new Solution();
    //     System.out.println(sol.minCut("aab")); // 1
    // }
}

Line Notes

boolean[][] palindrome = new boolean[n][n];2D array to store palindrome info

for (int i = n - 1; i >= 0; i--) {Fill palindrome table bottom-up

if (s.charAt(i) == s.charAt(j) && (j - i < 2 || palindrome[i + 1][j - 1])) {Palindrome check using smaller substring

Integer[] memo = new Integer[n];Memo array to cache results

if (memo[start] != null) return memo[start];Return cached result if available

for (int end = start; end < s.length(); end++) {Try all palindrome substrings starting at start

memo[start] = minCuts;Cache computed minimum cuts

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

class Solution {
public:
    int minCut(string s) {
        int n = s.size();
        vector<vector<bool>> palindrome(n, vector<bool>(n, false));
        for (int i = n - 1; i >= 0; --i) {
            for (int j = i; j < n; ++j) {
                if (s[i] == s[j] && (j - i < 2 || palindrome[i + 1][j - 1])) {
                    palindrome[i][j] = true;
                }
            }
        }
        vector<int> memo(n, -2);
        return dfs(s, 0, palindrome, memo);
    }

private:
    int dfs(const string& s, int start, const vector<vector<bool>>& palindrome, vector<int>& memo) {
        if (start == s.size()) return -1;
        if (memo[start] != -2) return memo[start];
        int minCuts = INT_MAX;
        for (int end = start; end < s.size(); ++end) {
            if (palindrome[start][end]) {
                int cuts = 1 + dfs(s, end + 1, palindrome, memo);
                if (cuts < minCuts) minCuts = cuts;
            }
        }
        memo[start] = minCuts;
        return minCuts;
    }
};

// int main() {
//     Solution sol;
//     cout << sol.minCut("aab") << endl; // 1
//     return 0;
// }

Line Notes

vector<vector<bool>> palindrome(n, vector<bool>(n, false));2D vector to store palindrome info

for (int i = n - 1; i >= 0; --i) {Fill palindrome table bottom-up

if (s[i] == s[j] && (j - i < 2 || palindrome[i + 1][j - 1])) {Palindrome check using smaller substring

vector<int> memo(n, -2);Memo vector initialized with sentinel to indicate uncomputed

if (memo[start] != -2) return memo[start];Return cached result if available

for (int end = start; end < s.size(); ++end) {Try all palindrome substrings starting at start

memo[start] = minCuts;Cache computed minimum cuts

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

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

    const memo = new Array(n).fill(undefined);
    function dfs(start) {
        if (start === n) return -1;
        if (memo[start] !== undefined) return memo[start];
        let minCuts = Infinity;
        for (let end = start; end < n; end++) {
            if (palindrome[start][end]) {
                let cuts = 1 + dfs(end + 1);
                if (cuts < minCuts) minCuts = cuts;
            }
        }
        memo[start] = minCuts;
        return minCuts;
    }

    return dfs(0);
};

// console.log(minCut("aab")); // 1

Line Notes

const palindrome = Array.from({length: n}, () => Array(n).fill(false));2D array for palindrome info

for (let i = n - 1; i >= 0; i--) {Fill palindrome table bottom-up

if (s[i] === s[j] && (j - i < 2 || palindrome[i + 1][j - 1])) {Palindrome check using smaller substring

const memo = new Array(n).fill(undefined);Memo array to cache results

if (memo[start] !== undefined) return memo[start];Return cached result if available

for (let end = start; end < n; end++) {Try all palindrome substrings starting at start

memo[start] = minCuts;Cache computed minimum cuts

⏱

Complexity

TimeO(n^2) for palindrome table + O(n^2) for recursion with memo

SpaceO(n^2) for palindrome table + O(n) for memo and recursion stack

Precomputing palindrome substrings takes O(n^2), and each index is computed once in recursion with O(n) substring tries.

💡 For n=1000, this means about 1 million operations, which is feasible.

Interview Verdict: Accepted

This approach is efficient enough for typical interview constraints and demonstrates DP mastery.

🧠

Tabulation (Bottom-Up DP with Palindrome Table)

💡 Tabulation builds the solution iteratively, which is often easier to debug and preferred in interviews for clarity and efficiency.

Intuition

Precompute palindrome substrings, then fill dp array from left to right, computing minimum cuts for each prefix.

Algorithm

1. Precompute palindrome table for all substrings.
2. Initialize dp array where dp[i] = max cuts (i).
3. Iterate over string indices i from 0 to n-1.
4. For each i, check all j ≤ i where s[j..i] is palindrome and update dp[i] = min(dp[i], dp[j-1] + 1).
5. Return dp[n-1] as the minimum cuts for entire string.

💡 This approach ensures all subproblems are solved before they are needed, avoiding recursion overhead.

Recurrence:dp[i] = min_{0 ≤ j ≤ i} (dp[j-1] + 1) if s[j..i] is palindrome, else dp[i] = i

</>

Code

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

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

    dp = [0]*n
    for i in range(n):
        if palindrome[0][i]:
            dp[i] = 0
        else:
            dp[i] = i
            for j in range(1, i+1):
                if palindrome[j][i]:
                    dp[i] = min(dp[i], dp[j-1] + 1)
    return dp[-1]

Line Notes

palindrome = [[False]*n for _ in range(n)]Initialize palindrome table

for i in range(n-1, -1, -1):Fill palindrome table bottom-up

if s[i] == s[j] and (j - i < 2 or palindrome[i+1][j-1]):Palindrome check

dp = [0]*nInitialize dp array for minimum cuts

if palindrome[0][i]:If substring s[0..i] is palindrome, no cuts needed

dp[i] = iInitialize dp[i] with max cuts (worst case)

for j in range(1, i+1):Try all partitions ending at i

dp[i] = min(dp[i], dp[j-1] + 1)Update dp[i] with minimum cuts

public class Solution {
    public int minCut(String s) {
        int n = s.length();
        boolean[][] palindrome = 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 || palindrome[i + 1][j - 1])) {
                    palindrome[i][j] = true;
                }
            }
        }
        int[] dp = new int[n];
        for (int i = 0; i < n; i++) {
            if (palindrome[0][i]) {
                dp[i] = 0;
            } else {
                dp[i] = i;
                for (int j = 1; j <= i; j++) {
                    if (palindrome[j][i]) {
                        dp[i] = Math.min(dp[i], dp[j - 1] + 1);
                    }
                }
            }
        }
        return dp[n - 1];
    }

    // public static void main(String[] args) {
    //     Solution sol = new Solution();
    //     System.out.println(sol.minCut("aab")); // 1
    // }
}

Line Notes

boolean[][] palindrome = new boolean[n][n];2D palindrome table

for (int i = n - 1; i >= 0; i--) {Fill palindrome table bottom-up

if (s.charAt(i) == s.charAt(j) && (j - i < 2 || palindrome[i + 1][j - 1])) {Palindrome check

int[] dp = new int[n];DP array for minimum cuts

if (palindrome[0][i]) {No cuts if s[0..i] palindrome

dp[i] = i;Initialize dp[i] with max cuts

for (int j = 1; j <= i; j++) {Try all partitions ending at i

dp[i] = Math.min(dp[i], dp[j - 1] + 1);Update dp[i] with minimum cuts

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

class Solution {
public:
    int minCut(string s) {
        int n = s.size();
        vector<vector<bool>> palindrome(n, vector<bool>(n, false));
        for (int i = n - 1; i >= 0; --i) {
            for (int j = i; j < n; ++j) {
                if (s[i] == s[j] && (j - i < 2 || palindrome[i + 1][j - 1])) {
                    palindrome[i][j] = true;
                }
            }
        }
        vector<int> dp(n, 0);
        for (int i = 0; i < n; ++i) {
            if (palindrome[0][i]) {
                dp[i] = 0;
            } else {
                dp[i] = i;
                for (int j = 1; j <= i; ++j) {
                    if (palindrome[j][i]) {
                        dp[i] = min(dp[i], dp[j - 1] + 1);
                    }
                }
            }
        }
        return dp[n - 1];
    }
};

// int main() {
//     Solution sol;
//     cout << sol.minCut("aab") << endl; // 1
//     return 0;
// }

Line Notes

vector<vector<bool>> palindrome(n, vector<bool>(n, false));2D palindrome table

for (int i = n - 1; i >= 0; --i) {Fill palindrome table bottom-up

if (s[i] == s[j] && (j - i < 2 || palindrome[i + 1][j - 1])) {Palindrome check

vector<int> dp(n, 0);DP array for minimum cuts

if (palindrome[0][i]) {No cuts if s[0..i] palindrome

dp[i] = i;Initialize dp[i] with max cuts

for (int j = 1; j <= i; ++j) {Try all partitions ending at i

dp[i] = min(dp[i], dp[j - 1] + 1);Update dp[i] with minimum cuts

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

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

    const dp = new Array(n).fill(0);
    for (let i = 0; i < n; i++) {
        if (palindrome[0][i]) {
            dp[i] = 0;
        } else {
            dp[i] = i;
            for (let j = 1; j <= i; j++) {
                if (palindrome[j][i]) {
                    dp[i] = Math.min(dp[i], dp[j - 1] + 1);
                }
            }
        }
    }
    return dp[n - 1];
};

// console.log(minCut("aab")); // 1

Line Notes

const palindrome = Array.from({length: n}, () => Array(n).fill(false));2D palindrome table

for (let i = n - 1; i >= 0; i--) {Fill palindrome table bottom-up

if (s[i] === s[j] && (j - i < 2 || palindrome[i + 1][j - 1])) {Palindrome check

const dp = new Array(n).fill(0);DP array for minimum cuts

if (palindrome[0][i]) {No cuts if s[0..i] palindrome

dp[i] = i;Initialize dp[i] with max cuts

for (let j = 1; j <= i; j++) {Try all partitions ending at i

dp[i] = Math.min(dp[i], dp[j - 1] + 1);Update dp[i] with minimum cuts

⏱

Complexity

TimeO(n^2) for palindrome table + O(n^2) for dp filling

SpaceO(n^2) for palindrome table + O(n) for dp array

Two nested loops for palindrome and dp each take O(n^2), total O(n^2).

💡 For n=1000, this is about 1 million operations, efficient for interviews.

Interview Verdict: Accepted

This is the standard optimal solution for this problem in interviews.

🧠

Space Optimized DP (1D DP with Center Expansion Palindrome Check)

💡 This approach reduces space by avoiding the 2D palindrome table, checking palindromes on the fly using center expansion.

Intuition

Expand around each center to find palindromes and update dp array for minimum cuts dynamically.

Algorithm

1. Initialize dp array where dp[i] = i (max cuts).
2. For each index, expand around center for odd length palindromes.
3. For each palindrome found, update dp[end] with minimum cuts.
4. Repeat expansion for even length palindromes.
5. Return dp[n-1] as minimum cuts.

💡 Center expansion avoids O(n^2) space for palindrome table, updating dp in place.

Recurrence:dp[end] = min(dp[end], dp[start-1] + 1) for palindrome s[start..end]

</>

Code

def minCut(s: str) -> int:
    n = len(s)
    dp = [i for i in range(n)]

    for center in range(n):
        # Odd length palindromes
        left, right = center, center
        while left >= 0 and right < n and s[left] == s[right]:
            dp[right] = 0 if left == 0 else min(dp[right], dp[left - 1] + 1)
            left -= 1
            right += 1

        # Even length palindromes
        left, right = center, center + 1
        while left >= 0 and right < n and s[left] == s[right]:
            dp[right] = 0 if left == 0 else min(dp[right], dp[left - 1] + 1)
            left -= 1
            right += 1

    return dp[-1]

Line Notes

dp = [i for i in range(n)]Initialize dp with max cuts (worst case)

for center in range(n):Expand palindromes around each center

while left >= 0 and right < n and s[left] == s[right]:Check palindrome by expanding

dp[right] = 0 if left == 0 else min(dp[right], dp[left - 1] + 1)Update dp with minimum cuts

left -= 1; right += 1Expand palindrome boundaries

public class Solution {
    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++) {
            // Odd length
            int left = center, right = center;
            while (left >= 0 && right < n && s.charAt(left) == s.charAt(right)) {
                dp[right] = (left == 0) ? 0 : Math.min(dp[right], dp[left - 1] + 1);
                left--;
                right++;
            }

            // Even length
            left = center;
            right = center + 1;
            while (left >= 0 && right < n && s.charAt(left) == s.charAt(right)) {
                dp[right] = (left == 0) ? 0 : Math.min(dp[right], dp[left - 1] + 1);
                left--;
                right++;
            }
        }
        return dp[n - 1];
    }

    // public static void main(String[] args) {
    //     Solution sol = new Solution();
    //     System.out.println(sol.minCut("aab")); // 1
    // }
}

Line Notes

int[] dp = new int[n];Initialize dp array

for (int i = 0; i < n; i++) dp[i] = i;Max cuts initialization

for (int center = 0; center < n; center++) {Expand palindromes around centers

while (left >= 0 && right < n && s.charAt(left) == s.charAt(right)) {Check palindrome by expanding

dp[right] = (left == 0) ? 0 : Math.min(dp[right], dp[left - 1] + 1);Update dp with minimum cuts

left--; right++;Expand palindrome boundaries

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

class Solution {
public:
    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) {
            // Odd length
            int left = center, right = center;
            while (left >= 0 && right < n && s[left] == s[right]) {
                dp[right] = (left == 0) ? 0 : min(dp[right], dp[left - 1] + 1);
                --left;
                ++right;
            }

            // Even length
            left = center;
            right = center + 1;
            while (left >= 0 && right < n && s[left] == s[right]) {
                dp[right] = (left == 0) ? 0 : min(dp[right], dp[left - 1] + 1);
                --left;
                ++right;
            }
        }
        return dp[n - 1];
    }
};

// int main() {
//     Solution sol;
//     cout << sol.minCut("aab") << endl; // 1
//     return 0;
// }

Line Notes

vector<int> dp(n);Initialize dp array

for (int i = 0; i < n; ++i) dp[i] = i;Max cuts initialization

for (int center = 0; center < n; ++center) {Expand palindromes around centers

while (left >= 0 && right < n && s[left] == s[right]) {Check palindrome by expanding

dp[right] = (left == 0) ? 0 : min(dp[right], dp[left - 1] + 1);Update dp with minimum cuts

--left; ++right;Expand palindrome boundaries

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

    for (let center = 0; center < n; center++) {
        // Odd length
        let left = center, right = center;
        while (left >= 0 && right < n && s[left] === s[right]) {
            dp[right] = left === 0 ? 0 : Math.min(dp[right], dp[left - 1] + 1);
            left--;
            right++;
        }

        // Even length
        left = center;
        right = center + 1;
        while (left >= 0 && right < n && s[left] === s[right]) {
            dp[right] = left === 0 ? 0 : Math.min(dp[right], dp[left - 1] + 1);
            left--;
            right++;
        }
    }
    return dp[n - 1];
};

// console.log(minCut("aab")); // 1

Line Notes

const dp = Array.from({length: n}, (_, i) => i);Initialize dp with max cuts

for (let center = 0; center < n; center++) {Expand palindromes around centers

while (left >= 0 && right < n && s[left] === s[right]) {Check palindrome by expanding

dp[right] = left === 0 ? 0 : Math.min(dp[right], dp[left - 1] + 1);Update dp with minimum cuts

left--; right++;Expand palindrome boundaries

⏱

Complexity

TimeO(n^2) due to palindrome expansions around centers

SpaceO(n) for dp array

Each center expands at most n times, total O(n^2). Space is reduced to O(n) from O(n^2).

💡 For n=1000, this is about 1 million operations but uses much less memory.

Interview Verdict: Accepted

This is a space-optimized solution preferred when memory is constrained.

📊

All Approaches - One-Glance Tradeoffs

💡 The tabulation or space optimized approach is best to code in interviews due to clarity and efficiency.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(2^n * n)	O(n) recursion stack	Yes (deep recursion)	No	Mention only - never code
2. Memoization with Palindrome Table	O(n^2)	O(n^2)	No (memoization)	Yes	Good to mention and code if comfortable
3. Tabulation (Bottom-Up DP)	O(n^2)	O(n^2)	No	Yes	Preferred approach to code
4. Space Optimized (Center Expansion)	O(n^2)	O(n)	No	Yes, with extra bookkeeping	Good for follow-up or memory constrained

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding all approaches, and learn how to explain your thought process clearly in interviews.

How to Present

Clarify the problem and constraints.Explain the brute force approach and its inefficiency.Introduce memoization with palindrome preprocessing.Present the bottom-up tabulation solution.Optionally discuss space optimization if time permits.Write clean code and test with examples.

Time Allocation

Clarify: 2min → Approach: 5min → Code: 10min → Test: 3min. Total ~20min

What the Interviewer Tests

Understanding of palindrome checking, dynamic programming state definition, optimization from recursion to DP, and code correctness.

Common Follow-ups

• How to reconstruct the palindrome partitions? → Use parent pointers to track cuts.
• Can we optimize palindrome checking further? → Use Manacher's algorithm for O(n) palindrome detection.

💡 These follow-ups test deeper understanding and ability to extend solutions.

🔍

Pattern Recognition

When to Use

1) Problem involves partitioning a string 2) Substrings must satisfy palindrome property 3) Minimize cuts or partitions 4) Overlapping subproblems with optimal substructure

Signature Phrases

'partition s such that every substring is a palindrome''minimum cuts needed for palindrome partitioning'

NOT This Pattern When

Problems that ask for longest palindromic subsequence or substring without partitioning are different patterns.

Similar Problems

Palindrome Partitioning I - find all palindrome partitionsLongest Palindromic Substring - find longest palindrome substring

Practice

1. Consider the following code snippet for counting distinct subsequences of t in s. What is the final returned value when s = "abc" and t = "ac"?

easy

A. 0

B. 1

C. 3

D. 2

Solution

1. Step 1: Trace dp array updates for s="abc", t="ac"

   Initialize dp=[1,0,0]. Iteration i=1 (s[0]='a'): j=2 no match, j=1 matches t[0]='a', dp[1]+=dp[0]=1 -> dp=[1,1,0].

2. Step 2: Continue tracing for i=2 (s[1]='b') and i=3 (s[2]='c')

   i=2 no matches, dp unchanged. i=3 matches t[1]='c', dp[2]+=dp[1]=0+1=1 -> dp=[1,1,1]. Final dp[n]=dp[2]=1.

3. Step 3: Count all subsequences matching "ac"

   Subsequences: "ac" only, total 1.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   dp array correctly counts 1 subsequence [OK]

Hint: Trace dp array backward updates carefully [OK]

Common Mistakes:

• Off-by-one errors in indices
• Forgetting to iterate j backward

2. You are given two strings and want to transform them into the same string by deleting characters from either string. The cost of deleting a character is its ASCII value, and the goal is to minimize the total deletion cost. Which algorithmic approach guarantees finding the minimum total ASCII delete sum?

easy

A. Dynamic programming based on the longest common subsequence (LCS) pattern extended to track ASCII sums

B. A greedy approach that deletes characters with the smallest ASCII values first

C. Sorting both strings and deleting characters that do not appear in both

D. Pure brute force recursion without memoization or pruning

Solution

1. Step 1: Understand problem as LCS variant

   The problem requires minimizing ASCII deletion cost to make strings equal, which relates to maximizing ASCII sum of common subsequence.

2. Step 2: Identify DP pattern

   Dynamic programming that extends LCS by tracking ASCII sums can optimally solve this, unlike greedy or brute force which are inefficient or incorrect.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   DP with LCS extension handles all cases optimally [OK]

Hint: Minimize deletions by maximizing ASCII sum of common subsequence [OK]

Common Mistakes:

• Thinking greedy deletion of smallest ASCII chars is optimal

3. You are given two integer arrays and want to connect pairs of equal integers with lines such that no two lines cross. Which algorithmic approach guarantees finding the maximum number of such uncrossed lines?

easy

A. A greedy approach that connects the first matching pair found and skips overlapping pairs

B. Dynamic programming that finds the longest common subsequence between the two arrays

C. A depth-first search exploring all possible pairs without memoization

D. Sorting both arrays and then matching elements in order

Solution

1. Step 1: Understand problem constraints

   The problem requires maximizing non-crossing lines connecting equal integers, which is equivalent to finding the longest common subsequence (LCS) between the two arrays.

2. Step 2: Evaluate approaches

   Greedy and sorting approaches fail because they do not consider all subsequence possibilities and can produce crossing lines. DFS without memoization is correct but inefficient. DP for LCS guarantees optimal solution efficiently.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   DP for LCS is the classic solution for maximum uncrossed lines [OK]

Hint: Maximum uncrossed lines = longest common subsequence [OK]

Common Mistakes:

• Thinking greedy or sorting suffices
• Ignoring subsequence order constraints

4. You are given a string s and a dictionary of words. You need to find all possible sentences where s can be segmented into a sequence of dictionary words. Which approach guarantees finding all valid sentences efficiently without redundant recomputation?

easy

A. Dynamic programming with bottom-up tabulation and backtracking to build all sentences

B. Greedy algorithm that picks the longest matching word at each step

C. Pure brute force recursion without memoization

D. Top-down recursion without caching intermediate results

Solution

1. Step 1: Understand problem requirements

   The problem requires enumerating all possible valid sentences, not just checking existence or counting.

2. Step 2: Evaluate approaches

   Greedy fails because it may miss valid segmentations. Pure recursion without memoization leads to exponential recomputation. Top-down recursion without caching also recomputes subproblems. Bottom-up DP with backtracking efficiently builds all solutions by storing intermediate results.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Bottom-up DP with backtracking enumerates all sentences efficiently [OK]

Hint: Bottom-up DP with backtracking enumerates all solutions [OK]

Common Mistakes:

• Thinking greedy or pure recursion suffices for all sentences

5. Examine the following buggy code snippet for wildcard matching using space-optimized DP. Which line contains the subtle bug that causes incorrect results on empty strings or patterns?

medium

A. Line 14: curr[j] = curr[j - 1] or prev[j]

B. Line 10: curr = [False] * (n + 1) initialization

C. Line 6: prev[j] = True instead of prev[j] = prev[j - 1]

D. Line 17: curr[j] = prev[j - 1]

Solution

1. Step 1: Analyze initialization of prev array for '*' characters

   Line 6 sets prev[j] = True unconditionally when p[j-1] == '*', which incorrectly assumes all prefixes match.

2. Step 2: Correct initialization logic

   It should propagate previous state: prev[j] = prev[j - 1], ensuring '*' can match empty sequence only if previous prefix matched.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Incorrect initialization causes false positives on empty strings [OK]

Hint: Initialization must propagate previous True states for '*' [OK]

Common Mistakes:

• Setting prev[j] = True blindly
• Ignoring empty string edge cases
• Confusing '*' handling in initialization