watching the old video yesterday and barely understanding then watching today and getting it within 5 mins shows how much u improved as a teacher props to u man!
The first thing I did was make a prefix tree and dfs, and that basically only worked for the first few cases until it used too much memory. Then, I used a default dict to store a tuple with the first and last index of every letter (a-z) (using find and rfind), and made a set of all chars between those two indices, and summed the length of the sets for every pair of indices.
Thanks to you, I was able to solve this question on my own using bit manipulation, because I had watched one of your videos in which you told how to use bit manipulation instead of hashmap to store count of characters.
I think that your dry run really helps solidify the understanding of the algorithm as well as helps support the time complexity explanation, so I am not against you doing dry runs for some problems.
I over thought this problem and wasted like 10 minutes, but took a step back and saw the intuition: Find the first and last occurrence of each character in the string. Count all unique chars in between them. class Solution: def countPalindromicSubsequence(self, s: str) -> int: m = {} for i, char in enumerate(s): if char in m: m[char][1] = i else: m[char] = [i, i] ans = 0 for a, b in m.values(): ans += len(set(s[a + 1: b]) return ans
I don't get why we would use a set for left part if we are not searching for a particular element but just reading through every element in it? Wouldn't a simple list suffice?
I have went through 260 problems and still was unable to solve this on my own. I dont even know how one would come up with the intuition to even arrive at this solution. There is no end to when Ill be comfortable solving stuff like this on my own yet :/
In regards to time complexity, we are not concerned about the absolute time it takes to process data. What we are concerned about is how much does the time change according to the size of the data. 26 * N is still N because N simply means a linear change.
@@15ag34 The entire reason big O exists is to talk about performance in a way that ignores constants. More than big O should be considered when caring about performance, but that is a separate issue that should be taught separately. Teaching big O to 'include the constants' inherently doesn't make sense and would lead to more confusion.
AI can only solve the questions that are already solved or when they are trivial. Try giving AI Leetcode contest question or any other contest question of decent level and watch it will shit itself.
I actually like your dry runs, really helps cement the thought behind the algo!
Love the dry runs. Please keep doing them
Please don't stop doing dry runs, it makes the algorithm so much more clearer.
watching the old video yesterday and barely understanding then watching today and getting it within 5 mins shows how much u improved as a teacher props to u man!
man we love your videos, never worry about the length you always explain the best way.
"Back when I was still unemployed"...😂😂😂😂🤣🤣
Dry run is actually very helpful.
The first thing I did was make a prefix tree and dfs, and that basically only worked for the first few cases until it used too much memory.
Then, I used a default dict to store a tuple with the first and last index of every letter (a-z) (using find and rfind), and made a set of all chars between those two indices, and summed the length of the sets for every pair of indices.
Thanks to you, I was able to solve this question on my own using bit manipulation, because I had watched one of your videos in which you told how to use bit manipulation instead of hashmap to store count of characters.
We ❤ dry runs regardless of the length of the video, please keep em!
Loved your dry run part
I think that your dry run really helps solidify the understanding of the algorithm as well as helps support the time complexity explanation, so I am not against you doing dry runs for some problems.
Code solution in other languages: neetcode.io/solutions/unique-length-3-palindromic-subsequences
I like that your solutions are simple and just work
Watched the old video a couple of hours back. This problem is one of my favourites.
Very good approach thank you man ♂️
I over thought this problem and wasted like 10 minutes, but took a step back and saw the intuition:
Find the first and last occurrence of each character in the string.
Count all unique chars in between them.
class Solution:
def countPalindromicSubsequence(self, s: str) -> int:
m = {}
for i, char in enumerate(s):
if char in m:
m[char][1] = i
else:
m[char] = [i, i]
ans = 0
for a, b in m.values():
ans += len(set(s[a + 1: b])
return ans
Best Dry Run
I think we can remove 26 multiplier to n and have exact n by some bitmasking things
I still haven't learned any of the data structure stuff. Opening up leetcode makes me feel like an actual ape.
I don't get why we would use a set for left part if we are not searching for a particular element but just reading through every element in it? Wouldn't a simple list suffice?
To eliminate duplicates, guaranteeing the loop is O(26)
@ thanks mate.
heyy bro ! Solve the leetcode 798 , i want your approach because no one is telling their approach correctly ... could you do ?? we reallyy needed !
I found the iterating between first and last indices to be simpler than this approach.
🐐🙇🏻♂
There are solutions in 30ms.. how is this efficient? What are those solutions that run like 50x faster?
Would this be sliding window?
No i guess, because its a subsequence not subarray
I have went through 260 problems and still was unable to solve this on my own. I dont even know how one would come up with the intuition to even arrive at this solution. There is no end to when Ill be comfortable solving stuff like this on my own yet :/
Does anybody else start with a rather brute force solution and then optimizes from that?
0th view
I guess its not exactly O(N), its like 26 * O(N) as there can be upto 26 characters in set, but then it is equal to O(N) itself.
In regards to time complexity, we are not concerned about the absolute time it takes to process data. What we are concerned about is how much does the time change according to the size of the data. 26 * N is still N because N simply means a linear change.
@@15ag34 The entire reason big O exists is to talk about performance in a way that ignores constants. More than big O should be considered when caring about performance, but that is a separate issue that should be taught separately. Teaching big O to 'include the constants' inherently doesn't make sense and would lead to more confusion.
@@15ag34 since when did we care about real world problems when solving leetcode problems
Big O notation ignores constant terms. 1 million * O(n) = O(n). That's the point of the notation.
Why do we need to multiply by 26? I mean there are 26 characters, but what is the reasoning?
how does it feel knowing your life's work can be solved with AI?
Can AI make videos like mine yet?
@@NeetCodeIO and even if it could, Id rather have a concise human explain it rather than a robot .
@andrewjontry bro appreciate this great man's work. no need to hate in the comments.
AI can only solve the questions that are already solved or when they are trivial. Try giving AI Leetcode contest question or any other contest question of decent level and watch it will shit itself.
@@eznx616 Actually o3 with high test time compute is a better competition coder than pretty much anyone any of us has ever met, unfortunately.