VALID PALINDROME III | LEETCODE 1216 | PYTHON MEMOIZED DFS SOLUTION

[@InterviewDose]

I always say BFS approach is easy for every solution but this one definitely DFS Thanks.

[@hangchen]

1 day ago??? Just about the time for me! Thank you!!!!

[@crackfaang]

Obviously with my infinite wisdom I foresaw you would need this question and made the video 😂

[@hangchen]

​ @crackfaang I feel honored that you made the video specifically for me. You are my Nostradamus 🙌 I must grab its essence

[@hangchen]

@@crackfaang Thank you for the solution! You code is both intuitive and easy to understand! After fully understanding the logic, I figured I can further reduce the code to
```
class Solution:
def isValidPalindrome(self, s: str, k: int) -> bool:
memo = {}
def helper(i, j, k):
if k < 0:
return False
if (i, j, k) in memo:
return memo[(i, j, k)] # can also just `return False`
else:
while i < j:
if s[i] != s[j]:
memo[(i, j, k)] = helper(i + 1, j, k - 1) or helper(i, j - 1, k - 1)
return memo[(i, j, k)]
i += 1
j -= 1
return True
return helper(0, len(s) - 1, k)
```
Here are my mindflows
1. We could actually remove is_palindrome() and use the same palindrome checking logic when k == 0. So when k == 0, I let the code continue and make use of the panlindrome checking logic defined in helper(), instead of is_palindrome()
2. Now since we we do not need the `if not k` base case, we need a new base case to stop the recursion. The one I figured out is `if k < 0: return False`, because it's technically correct that we should not continue with checking or exploring more palindromes when k is exhausted
3. I figured that the memo is actually only used to store cases where (i, j, k) lead to False. If we find a `True` palindrome, we can just return it all the way up. So I removed the line `memo[(i, j, k)] = True` and make it directly return True. I think this way of writing the palindrome checking logic is also more consistent with Valid Palindrome II
4. Due to 2 and 3, we can further reduce the base case to `if k < 0 or (i, j, k) in memo: return False`
Based on 3, I also realized that we can also use set() as memo, but it's a minor implementation detail that doesn't affect the overall time and space complexity
The overall logic is exactly the same and the time and space complexity should still be O(N^2). I tested the code and it passed with similar time and space usage. Hopefully the reduced version of the code is more easier to "memorize" 😆

[@crackfaang]

@@hangchen Yea we really don't actually need the palindrome checker helper function. Either way the execution in the code will be the same whether we do it in the helper or in the DFS.
100% agree that it makes the code cleaner and simpler.

[@hangchen]

@@crackfaang Thanks for your continuous efforts to provide these free and helpful coding videos! I've been using them to prepare for my interviews since the start of 2023. You truly helped me a lot in improving my coding skills. I have a hard-won interview opportunity coming up soon and hope this time I can nail it!

[@landocodes]

.05 subs from 10k. Well deserved man.

[@crackfaang]

25k next milestone :)

[@christine3849]

I had a question about how the runtime is O(n^2). I would think that because the memo can contain n x n x k items, the number of times we enter recursive function is k * O(n^2). But inside of the recursive function, we also check for self.isPalindrome which is, at worst, O(n) runtime if j - i = n - 1 or similar. Then it seems the total runtime should be O(n^3)?

[@davidoh0905]

How would you define what memo memoizes here? Also, what type of repetition can it help alleviate?
I was thinking may be if (i, j, 10) = True, then (i, j, 11) should automatically be considered True
Also, if (i,j, 9) turns out to be true, it would be good if this memo was being stored with a value like (i, j): 9. And if we only have a fail case, we could do (i, j): -1
I have not come up with a solution using memo representation as (i, j): smallest K that allows for i,j,k to be valid just yet.
But wanted to share this thought cause strictly assigning boolean to (i, j, k) seems it could be limited in terms of saving repetitions.
Let me know if this intuition makes sense! Thank you!

[@nikhilkshirsagar1844]

Are we sure we need DP here? There don't seem to be repeated solutions. Whenever we find a mismatched pair of characters we make DFS calls and we return which means we process a pair of (i,j,k) only once.

[@shoaibakhtar9194]

Great video as always.
I came across another solution which is also very good, little tricky but still good one.
class Solution {
public boolean isValidPalindrome(String s, int k) {
int stringLength = s.length();
int[][] dp = new int[stringLength][stringLength];
// Initialize each character as a palindrome of length 1
for (int i = 0; i < stringLength; ++i) {
dp[i][i] = 1;
}
// Build the table in a bottom-up manner
for (int i = stringLength - 2; i >= 0; --i) {
for (int j = i + 1; j < stringLength; ++j) {
// If characters match, take the length from the diagonally lower cell and add 2
if (s.charAt(i) == s.charAt(j)) {
dp[i][j] = dp[i + 1][j - 1] + 2;
} else {
// If characters do not match, take the max from either side (ignoring one character)
dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
}
// If the palindrome length plus the allowed deletions covers the whole string length, it is valid
if (dp[i][j] + k >= stringLength) {
return true;
}
}
}

// If none of the substrings could be a palindrome with the given k, return false
return false;
}
}

[@shravanthimanohar9201]

This seems similar to LCS DP solution but with some extra calc

[@kedikeba]

I think the explaination of the usage of (i, j, k) is still lacking

[@timo9madrid7]

can we do like recursively like this:
```python
class Solution:
def validPalindrome(self, s: str, k: int) -> bool:
l, r = 0, len(s) - 1
while l < r:
if s[l] == s[r]:
l += 1
r -= 1
else:
if k == 0:
return False

return self.validPalindrome(s[l+1:r+1], k-1) or self.validPalindrome(s[l:r], k-1)

return True
```

[@zacherypang1716]

Yeah. i arrived at the same solution. This has a lower runtime of O(N). No memoization needed.

[@ajvercueil8111]

​@@zacherypang1716 For this problem, it seems like the non-memoized DFS solutions TLE on testcase 44.

[@ajvercueil8111]

This solution TLEs now

[@mdmoinuddinchowdhury1318]

Is the time complexity O(n^2) or O(n^2*k) ?

[@SaiEswarBoda]

O(n^2*k)

[@awb19892]

instead of a boolean table, create an integer table representing min number of chars needed to delete to make S[i..j] a palindrome and return T[i, j]

[@PoRBvG]

this is DP. Top down DP.