Solving Amazon's 2024 Most Asked Coding Question

Check out my interview prep platform for mastering the coding patterns!
📢 Interview prep platform: algoswithmichael.com
🔗 Social 🔗
🎧 Join the community Discord: / discord
💰 Support me on Patreon: / michaelmuinos
🔗Follow me on LinkedIn: / michael-muinos
📂Follow me on Github: github.com/MichaelMuinos
⭐️ Timestamps ⭐️
00:00 - Problem Examples
03:29 - Brute Force
04:31 - Algorithm
10:45 - Code
15:36 - Time & Space Complexity

[@kmesh9]

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

[@allasbheen2634]

Explained great 👏👏👏

[@adilansari-hq9ge]

Awesome Video. I have been missing your videos Michel, please keep uploading.

[@isaacojigho4481]

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

[@danieladaniel2004]

I love the way you explain these problems.

[@kiranimmanni81]

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! 😊

[@kmesh9]

"invalid" is a hash map so I assume time complexity for it would be O(1)