# I'm sure my algo is O(N^2) here. but why i'm still getting TLE on "aaa....aaa" test case?

• HashMap<String, Integer> mapStringCost = new HashMap<String, Integer>();

``````public int minCut(String s) {
int cuts = s.length() - 1;
String ls = "";

if (isPalindrome(s))
return 0;

for (int i = 0; i < s.length(); i++){
ls += s.charAt(i);
if (isPalindrome(ls))
{
String lsub = s.substring(i+1);
if (lsub.isEmpty())
continue;

Integer subMinCut = mapStringCost.get(lsub);

if (subMinCut == null)
{
subMinCut = minCut(lsub);
mapStringCost.put(lsub, subMinCut);
}

if (cuts > subMinCut + 1)
cuts = subMinCut + 1;

}
if (cuts == 1)
return cuts; // s itself isn't palindrome when we are here, so if cuts is 1, we are already the best. return here.
}
return cuts;
}

private boolean isPalindrome(String s)
{
if (s.isEmpty())
return true;
boolean isPalindrome2 = true;
for (int i = 0; i < s.length()/2; i++)
{
char sfront = s.charAt(i);
char sback = s.charAt(s.length() - i - 1);
if (sfront != sback)
{
// found bad sequence, bail
isPalindrome2 = false;
break;
}
}
return isPalindrome2;
}
``````
1. i'm using the hashmap to record the calculated mincuts for specific substring. this saved big, and serves the memoization part of the DP.
2. i only have 2 for loops in this code, the main loop each iteration, and the isPalindrome function has a lopp. worst case ( if it's is a palindrome) will loop through entire substring.

any suggestion i can improve further?

• Your solution is not O(N^2), is O(N^3).

``````public int count = 0;
public int count_of_minCut = 0;
public int minCut(String s) {
int cuts = s.length() - 1;
String ls = "";
count_of_minCut++;

if (isPalindrome(s))
return 0;

for (int i = 0; i < s.length(); i++){
ls += s.charAt(i);
count++;
if (isPalindrome(ls))
{
``````

If you edit your code as I pasted above, you can see that the code calls minCut s.length() times.

For each minCut called, it will iterate through each character in s and test if ls is palindrome, thus O(N^2) time complexity for each mincut call.

Therefore your solution will is O(N^3) in time complexity.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.