Let's now discuss the space and time complexity of the memoization approach for solving the palindrome
substrings question.
So because we are using this DP table over here, the space complexity of this approach is going to
be of the order of n square.
Also notice the memoization approach is still a recursive approach.
So we will be using space on the recursive call stack.
But the space used over there will be less than n square.
So that's why finally the space complexity of this approach is of the order of n square.
And the time complexity of this approach is also of the order of n square.
Now again, why is this the case?
Because we will be computing either true or false for a substring only once, and then we would store
it in the DP table.
Now the number of substrings will be of the order of n square.
Again why is this the case?
Notice over here there are n substrings of length one.
But we don't need to check whether these are palindromes, because we know that if a substring has just
one character, then it will be a palindrome.
Also, notice that when it comes to substrings of length two, we will have n minus one such substrings,
and in a similar manner we would have n minus two substrings of length equal to three.
And finally we would have one substring of length n okay.
So the total number of substrings that we would need to check is one plus two plus three etc. up to
n minus one.
And this is equal to n minus one into n divided by two.
And if you simplify this you will have an n square term, and therefore the total number of substrings
that we need to check is of the order of n square.
And we are checking each substring only once, and we will store whether it is a palindrome or not in
the DP table over here.
So that's why the time complexity of this approach is of the order of n square.