# TLE problem

• Hi guys!

My method to solve this problem is very straightforward and should be easy to understand. In my opinion, my method should be O(n^2) time complexity and O(n) space complexity. However, this method is never been accepted. Can anyone tell me why this is TLE. Here is my code. Thanks in advance.

``````public class Solution {
public int minCut(String s) {
if(s.length() == 0) return 0;
List<List<String>> list = new ArrayList<List<String>>();
helper(list, new ArrayList<String>(), s);
int min = s.length();
for(List<String> sublist : list) {
if(sublist.size() < min) {
min = sublist.size();
}
}
return min - 1;
}

public void helper(List<List<String>> list, List<String> tmp, String s) {
if(s.length() == 0) {
return;
}

for(int i = 0; i < s.length(); i++) {
if(isPalindrome(s.substring(0, i + 1))) {
helper(list, tmp, s.substring(i + 1));
tmp.remove(tmp.size() - 1);
}
}
}

public boolean isPalindrome(String s) {
int lo = 0;
int hi = s.length() - 1;

while(lo < hi) {
if(s.charAt(lo) != s.charAt(hi)) return false;
lo++;
hi--;
}
return true;
}
}``````

• Looks like your solution is just brute force....so you generate all possible palindrome partitions and find the minimum. Brute force solution is not O(n^2) time and O(n) space, but exponential. Try this input: aaaa...aaaa, which has all 'a', you should have better understanding of it.

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