```
Time complexity is O(n^2), space complexity is O(n^2) too, but really we only need O(n) space, because only one previous step will be used. I have a question though, in this case, do those space that is no longer used get garbage collected?
public String longestPalindrome(String s) {
if (s.length() <= 1) {
return s;
}
int[][] matrix = new int[s.length()][s.length()];
int max = 1, low = 0;
for (int i = 0; i < s.length(); i++) {
matrix[i][i] = 1;
}
for (int i = s.length() - 1; i >= 0; i--) {
for (int j = i + 1; j < s.length(); j++) {
if (j == i + 1) {
matrix[i][j] = (s.charAt(i) == s.charAt(j)) ? 2 : 0;
} else {
matrix[i][j] = (s.charAt(i) == s.charAt(j) && matrix[i + 1][j - 1] !=0) ? matrix[i + 1][j - 1] + 2 : 0;
}
if (matrix[i][j] > max) {
max = matrix[i][j];
low = i;
}
}
}
return s.substring(low, low + max);
}
```