← All questions
Coding

Palindrome partitioning II

Asked atAmazonMicrosoft
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
    }
}

go

func minCut(s string) int {

}
Stuck? Show a way to structure it+
  1. 01Precompute whether every substring is a palindrome.
  2. 02Let cuts[i] be the minimum cuts for prefix ending at i.
  3. 03For every palindromic suffix j..i, update from the prefix before j.
  4. 04Return cuts[n-1], with a palindrome prefix requiring zero cuts.

Reference answer

Then expect these follow-ups

  • How can center expansion reduce memory?

    Tests: optimization

  • How would you output an optimal partition?

    Tests: parent tracking

Free to read · better with Enzo

Practice this out loud with Enzo

Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.

Continue with EnzoSign up free

Next question