Coding

Palindrome partitioning II

Asked at

Amazon

Microsoft

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

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.

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

Input : s = "abaaba" Output : 0 Explanation : The complete string can be considered as a partition as the string itself is palindrome. There are other ways to partition the string but it requires more number of cuts.

Input : s = "abcd"

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

cpp

class Solution {
	public:
    	int minCut(string s){
    		//your code goes here
	    }
};

java

class Solution {
    int minCut(String s) {
        //your code goes here
    }
}

python

class Solution:
    def minCut(self, s):
        #your code goes here

javascript

class Solution {
    minCut(s) {
        //your code goes here
    }
}

csharp

class Solution {
    public int MinCut(string s) {
        //your code goes here
    }
}

func minCut(s string) int {

}

Stuck? Show a way to structure it+

01Precompute whether every substring is a palindrome.
02Let cuts[i] be the minimum cuts for prefix ending at i.
03For every palindromic suffix j..i, update from the prefix before j.
04Return cuts[n-1], with a palindrome prefix requiring zero cuts.

Reference answer

First determine palindromic substrings, either with a boolean table filled by increasing length or by expanding around centers. Then let cuts[i] be the minimum cuts needed for s[0..i]. If s[0..i] is a palindrome, cuts[i]=0; otherwise for every j>0 where s[j..i] is a palindrome, consider cuts[j-1]+1. The minimum is the answer. Both palindrome table and cut transitions are O(n^2), suitable for n=2000; the table uses O(n^2) memory. Avoid treating the number of palindrome pieces as the answer, since cuts equal pieces minus one.

Then expect these follow-ups

How can center expansion reduce memory?
Tests: optimization
How would you output an optimal partition?
Tests: parent tracking

Hiring now

Software engineer roles are open right now

landed applies to roles like these for you, on each company’s own site, with answers written for the role.

Get 5x interviews10 free auto-applies. No card.

Senior Software Engineer -.NET
Tyler Technologies · Annapolis, Maryland
Software Development Engineer II
SaaS Labs · Bengaluru, Karnataka, India
Advanced Software Engineer - Product Architect (Legal, Safety, and Risk)
Metropolitan Transportation Authority · New York, NY

Or practice this question first

Next question