text: # How to get from O(n^3) to O(n^2) ? Java Solution Sharing
  
  • I have been trapped by O(n^3) run time all the way till I finally found the correlation between Palindrome Partitioning and Palindrome Partitioning II.
  
  In Palindrome Partitioning, we are able to get every pair of (i,j), such that s.substring(i,j) is or is not a palindrome. And it's O(n^2) to get there.
  
  But if we are to trace on that 2D array to determine min cut, we are going into an O(2^n) recursive algorithm.
  
  Based on what we already know, the s.substring(i,j) is or is not a palindrome, which is a very useful information, can we in O(n^2) time get the min cut of s?
  
  The answer is another DP, whether you use a 2D array or a 1D array, you'll find that since we know whether s.substring(i,j) is or is not a palindrome, we can make each iteration O(1).
  
  Two separate DP with both running in O(n^2) time makes a O(n^2) algorithm.
  
  ``````public class Solution {
  public int minCut(String s) {
  // use DP to determine any palindrome substring
  boolean opt[][] = new boolean[s.length()][s.length()+1];
  // base case
  for(int i = 0;i < s.length();i++){
  opt[i][i+1] = true;
  opt[i][i] = true;
  }
  // iteration
  for(int i = 2;i <= s.length();i++)
  for(int j = 0;j+i <= s.length();j++)
  opt[j][j+i] = s.charAt(j)==s.charAt(j+i-1) && opt[j+1][j+i-1];
  
  // use DP to determine min cut
  int cut[] = new int[s.length()+1];
  for(int i = 1;i <= s.length();i++){
  if(opt[0][i])
  cut[i] = 0;
  else{
  cut[i] = i-1;
  for(int t = 1;t < i;t++){
  cut[i] = Math.min(cut[i],cut[t] + (opt[t][i]?1:i-t));
  }
  }
  }
  return cut[s.length()];
  
  }
  }``````
  
  • This post is deleted!
  
  • Great solution! But I'm a little confuse about the transform function.
  
  cut[i] = Math.min(cut[i], cut[t] + (opt[t][i] ? 1 : i - t));
  
  When opt[t][i] is false, just think substr(t, i - t) as a string with no palindrome inside ? I think it can be lower. Why does this solution works ?
  
  Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.
explanation: The text extract is a discussion about optimizing the runtime of an algorithm from O(n^3) to O(n^2) for the problem of finding the minimum cut in a string to partition it into palindromic substrings. It includes a Java solution and a follow-up question about a specific part of the code.
distilabel_metadata.content: Evaluate the user given text extract and determine if it contains a math question and optionally and answer to this question.
  
  Output rules:
  
  1. Briefly describe the document and mention if it contains a question or a question and answer.
  2. Finalize the output with: Label: no-question,question,question-and-answer,multiple-question,multiple-question-and-answer
distilabel_metadata.role: system
distilabel_metadata.content: # How to get from O(n^3) to O(n^2) ? Java Solution Sharing
  
  • I have been trapped by O(n^3) run time all the way till I finally found the correlation between Palindrome Partitioning and Palindrome Partitioning II.
  
  In Palindrome Partitioning, we are able to get every pair of (i,j), such that s.substring(i,j) is or is not a palindrome. And it's O(n^2) to get there.
  
  But if we are to trace on that 2D array to determine min cut, we are going into an O(2^n) recursive algorithm.
  
  Based on what we already know, the s.substring(i,j) is or is not a palindrome, which is a very useful information, can we in O(n^2) time get the min cut of s?
  
  The answer is another DP, whether you use a 2D array or a 1D array, you'll find that since we know whether s.substring(i,j) is or is not a palindrome, we can make each iteration O(1).
  
  Two separate DP with both running in O(n^2) time makes a O(n^2) algorithm.
  
  ``````public class Solution {
  public int minCut(String s) {
  // use DP to determine any palindrome substring
  boolean opt[][] = new boolean[s.length()][s.length()+1];
  // base case
  for(int i = 0;i < s.length();i++){
  opt[i][i+1] = true;
  opt[i][i] = true;
  }
  // iteration
  for(int i = 2;i <= s.length();i++)
  for(int j = 0;j+i <= s.length();j++)
  opt[j][j+i] = s.charAt(j)==s.charAt(j+i-1) && opt[j+1][j+i-1];
  
  // use DP to determine min cut
  int cut[] = new int[s.length()+1];
  for(int i = 1;i <= s.length();i++){
  if(opt[0][i])
  cut[i] = 0;
  else{
  cut[i] = i-1;
  for(int t = 1;t < i;t++){
  cut[i] = Math.min(cut[i],cut[t] + (opt[t][i]?1:i-t));
  }
  }
  }
  return cut[s.length()];
  
  }
  }``````
  
  • This post is deleted!
  
  • Great solution! But I'm a little confuse about the transform function.
  
  cut[i] = Math.min(cut[i], cut[t] + (opt[t][i] ? 1 : i - t));
  
  When opt[t][i] is false, just think substr(t, i - t) as a string with no palindrome inside ? I think it can be lower. Why does this solution works ?
  
  Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.
distilabel_metadata.role: user
distilabel_metadata.raw_output_q_a_detector_0: The text extract is a discussion about optimizing the runtime of an algorithm from O(n^3) to O(n^2) for the problem of finding the minimum cut in a string to partition it into palindromic substrings. It includes a Java solution and a follow-up question about a specific part of the code.
  
  Label: question-and-answer