# Why my O(n^2) code gets TLE using a HashMap

• I used double for loop to check each substring (0,i) for future use, and was trying to use a hash map to store the strings that I have already checked. So far I am pretty sure that my solution is O(n^2) but why am I getting TLE in the "aaa...........aaabbaaa......aa" test case? Does containsKey() and get() really takes only O(1) time? Thanks.

public class Solution {
public int minCut(String s) {
if (s.length() <= 1) {
return 0;
}
HashMap<String, Integer> palinStr = new HashMap<String, Integer>();
palinStr.put("", -1);
for (int i = 1; i <= s.length(); i++) {
int minimum = Integer.MAX_VALUE;
for (int j = 0; j < i; j++) {
int current;
String left = s.substring(0,j);
String right = s.substring(j,i);
if (palinStr.containsKey(right) || isPalindrome(right, palinStr)) {
current = palinStr.get(right) + palinStr.get(left) + 1;
minimum = Math.min(current, minimum);
}
}
palinStr.put(s.substring(0,i), minimum);
}
return palinStr.get(s);
}

public boolean isPalindrome(String s, HashMap<String, Integer> palinStr) {
if (palinStr.containsKey(s)) {
return palinStr.get(s) == 0;
}
int cursor1 = 0;
int cursor2 = s.length()-1;
while (cursor1 < cursor2) {
if (s.charAt(cursor1) != s.charAt(cursor2)) {
return false;
} else if (palinStr.containsKey(s.substring(cursor1 + 1, cursor2))) {
palinStr.put(s, 0);
return palinStr.get(s.substring(cursor1 + 1, cursor2)) == 0;
}
cursor1 ++;
cursor2 --;
}
palinStr.put(s, 0);
return true;
}

}

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