# 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.
The text passage discusses an algorithmic problem and its solution, specifically focusing on optimizing the runtime from O(n^3) to O(n^2) for the Palindrome Partitioning problem. It includes a Java code snippet and a question about a specific part of the code.
single_question
- the passage contains a single mathematical question regarding the correctness of a specific line of code in the algorithm. however, no explicit answer to this question is provided in the text.
Given a text passage, determine:
    1. If it contains a mathematical question (including word problems or calculations)
    2. If an answer to that mathematical question is provided in the text

First, describe the content structure you found in 1-2 sentences.

Then provide your analysis in the following format:
TYPE: <one of the following values>
- NO_QUESTION
- SINGLE_QUESTION
- SINGLE_QUESTION_WITH_ANSWER
- MULTIPLE_QUESTIONS
- MULTIPLE_QUESTIONS_WITH_ANSWERS
system
# 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.
user
The text passage discusses an algorithmic problem and its solution, specifically focusing on optimizing the runtime from O(n^3) to O(n^2) for the Palindrome Partitioning problem. It includes a Java code snippet and a question about a specific part of the code.

TYPE: SINGLE_QUESTION
- The passage contains a single mathematical question regarding the correctness of a specific line of code in the algorithm. However, no explicit answer to this question is provided in the text.