Freedom Trail - Leetcode 514 - Python 

bro single handedly saving my streak. thanks for doing this :)

These problem descriptions are getting out of hand

Only channel on whole youtube which is best not just solving leetcode problems but also to explaining the problem as much as simple possible with many approaches DAMM

another problem with dp vs greedy ... where greedy fails

Thank you Neetcode, I learned Algorithm from your series by watching the whole Medium playlist. Now I passed my Codility test and got the first internship, which I thought I couldn't 2 months ago XD

I am happy that atleast I was able to try the problem in the SMART way, and ofcourse failed 😂😂

python 80ms - recursion + memoization + binary search class Solution: def findRotateSteps(self, ring: str, key: str) -> int: @cache def dfs(r: int, k: int) -> int: if k == len(key): return 0 steps = math.inf for i in get_closest_indexes(r, key[k]): steps = min(steps, get_min_distance(r, i) + dfs(i, k + 1)) return 1 + steps def get_closest_indexes(i: int, char: str) -> Tuple[int]: if ring[i] == char: return (i,) char_indexes = indexes[char] if len(char_indexes) == 1: return tuple(char_indexes) l, r = 0, len(char_indexes) - 1 while l < r: m = l + (r - l) // 2 if char_indexes[m] < i: l = m + 1 else: r = m - 1 return ( char_indexes[l], char_indexes[l - 1] if char_indexes[l] > i \ else char_indexes[(l + 1) % len(char_indexes)] ) def get_min_distance(i: int, j: int) -> int: diff = abs(i - j) return min(diff, len(ring) - diff) indexes = defaultdict(list) for i, char in enumerate(ring): indexes[char].append(i) return dfs(0, 0)

Phenomenal explanation as always. Thank you

Neetcode, thank you for detailed explanation specially when using recursion. A decision tree really helps to divide and conquer the problem. By the way dp solution are better. Thanks 😊

Am I supposed to have a solution that works from the first try "normally"? because I always write a solution that works for basic cases and then I start finding bugs I didn't see after submitting the thing, I think that's because I don't completely see what my code is doing until I get a hint by the failed submissions that probably this part isn't working, how do you guys deal with this? is it just me or it's about me not trying to go over the code again and again to try and catch bugs before submitting the solution, if that's the case, is it really what should happens when coding in real life situations?

For the recursive solution with memoization, although it makes the code a little messier, you don't really need to consider all possible occurrences of a particular key character in the ring. Finding the first occurrence of the required character towards the left and the right and then recursively solving the rest of the problem is also adequate! But yeah great solution that helped me save my streak! Keep writing more neet code! :D

I just saw now that this is the same problem we'll have to solve if we tried to type a string using a wheel that contains letters if we have the same mechanism as the those old phone wheels, the only difference is that phone wheels has has only numbers and they appear only once, this is a more general situation

I recognise that it is DP problem, but I get stuck at the moment how to find circular offset, blain on me. After the moment you get the explanation I solved it by myself.

Solved it!!

The DP drawing is very helpful

21-1

I’m adept at problem solving complex technical issues)

Whoelse came up with Greedy solution and got suboptimal like me...

PLEASE SOLVE TODAY'S CONTEST'S PROBLEM "Find All Possible Stable Binary Arrays I" BECAUSE IT WAS SO SO DIFFICULT 😭😭😭😭

Really good!!!!

Thanks for the solution! If we come up with the caching solution and not the best optimal approach is it considered bad in an real interview? Can you kindly show/share code snippet for both caching solution and the optimal sol that you would do in a real FAANG interview? Love your videos❤

Please solve contest problems for leetcode it will be so beneficial your quality of explanation is what we want please please please

Please do yesterday's daily question i.e sum of distances in a tree, it seems like a really good question

this was a pretty cool problem

recursive 2state dp with memoization

Hii. I have a request. Please make a video on the problem "1915: Number of wonderful substrings". No matter how hard i try i could not understand the logic. I watch your videos and i think you can explain it to me. And i am pretty sure i will understand if you make a video on this problem. Please take it as a request. Thanks. love your videos

I need to practice more......

"wanna spend your life doing that" xD, tabulation gives me nightmares

To understand recursion you must first understand recursion

in desperate need for a good solution of 1915. Number of Wonderful Substrings cant find anywhere

Bro the video embed in your courses are not working

4:55 Sorry, but I still can’t see why trying every characters (those three 'b's) won’t make our solution more inefficient 😢 Can somebody explain to me 🙏

21:45 Martin Fowler wants to know your location.

I have a question would be thankful if someone can please explain. In recursive solution if c == key[k] min_dist = min(abs(r-i), len - abs(r-i)) why are we taking this minimum instead of trying out both the solutions, as taking the minimum won't make this approach greedy?

solved it w a heap and it worked 💀

Vault-tec 😂😂😂

where are you man?? 2 days no solutions

Wouldn't it be easier if we concatenated the string with itself to make the recurssive solution easier ?

btw in python you can just do res = inf or -inf its a shorter then float("inf")

The brute force is not easy at all 🥲