Good explanation, although it would've been good to clarify that it's not pointers moving backwards that allow us to skip most iterations from the bruteforce solution, but rather sliding window algorithm itself. You can reverse the solution and it would work perfectly as well - pointers go from left to right, but you do substrings from right to left (imo it would be a bit more intuitive to those already familiar with sliding window algorithm). You can even use something like ".endsWith(invalid[i])", though it would make time complexity a O(n*m*k), where k is length of the invalid array so with given constraints it would be worse, but generally might be better/same time complexity
Could you plz check following case: Forbidden=[de, le, e, mp] word=leetcodmpe Algo in video would give tcod as answer, but answer should be tcodm Am I missing something? Basically, thinking about matching substring of more than 1 length..
Hey Michael this was a great video and I really appreciate it. Could you please provide the link for the list of questions you got this question from. you showed the page briefly at the 0:07 sec mark. the link to all questions by amazon in 2024 would be very helpful
Hi Michael, that’s a great explanation, though I noticed a small correction needed for your time complexity calculation. You forgot to include `invalid.contains(substring)`, which has a complexity of O(K) in this case (where K is 10^5, the length of the forbidden substring). So, the corrected time complexity is: O(N) { O(M) { O(M) + O(K) } } Thus, the total time complexity is O(N * M * (M + K)), or more succinctly, O(N * M^2 * MK). Hope this helps clarify! 😊
Good explanation, although it would've been good to clarify that it's not pointers moving backwards that allow us to skip most iterations from the bruteforce solution, but rather sliding window algorithm itself. You can reverse the solution and it would work perfectly as well - pointers go from left to right, but you do substrings from right to left (imo it would be a bit more intuitive to those already familiar with sliding window algorithm).
You can even use something like ".endsWith(invalid[i])", though it would make time complexity a O(n*m*k), where k is length of the invalid array so with given constraints it would be worse, but generally might be better/same time complexity
Awesome Video. I have been missing your videos Michel, please keep uploading.
Could you plz check following case:
Forbidden=[de, le, e, mp]
word=leetcodmpe
Algo in video would give tcod as answer, but answer should be tcodm
Am I missing something?
Basically, thinking about matching substring of more than 1 length..
Hey Michael this was a great video and I really appreciate it. Could you please provide the link for the list of questions you got this question from. you showed the page briefly at the 0:07 sec mark. the link to all questions by amazon in 2024 would be very helpful
I love the way you explain these problems.
Explained great 👏👏👏
Hi Michael, that’s a great explanation, though I noticed a small correction needed for your time complexity calculation.
You forgot to include `invalid.contains(substring)`, which has a complexity of O(K) in this case (where K is 10^5, the length of the forbidden substring).
So, the corrected time complexity is:
O(N) {
O(M) {
O(M) + O(K)
}
}
Thus, the total time complexity is O(N * M * (M + K)), or more succinctly, O(N * M^2 * MK).
Hope this helps clarify! 😊
"invalid" is a hash map so I assume time complexity for it would be O(1)