Unique Length-3 Palindromic Subsequences | 2 Ways | Intuition | Leetcode 1930 | codestorywithMIK

[@dyashwanth9822]

11:24 yaha tak video dekhke thoda bahut intuition build hogaya aur Aapke intuition se mene efficient code likha bhai Really thank You so much bhai ❤. sach me bhai aapka samjhane ka tareeka unique hai This was my code s1 = set(s) Total = 0 for i in s1: Frontindex = s.index(i) Lastindex = s.rindex(i) Total += len(set(s[Frontindex+1:Lastindex])) return Total

[@codestorywithMIK]

So glad to hear. Thank you so much 😇🙏❤️

[@RUSTYYYYYYYYY]

same maine bhi kiya par c++ me

[@RUSTYYYYYYYYY]

class Solution { public: int countPalindromicSubsequence(string s) { unordered_set st; int cnt = 0; int n = s.length(); for(auto it:s) st.insert(it); for(auto it:st){ char ch = it; int start = 0 ; int end = n - 1; while(start < n){ if(s[start] == ch){ break; } start++; } while(end >= 0){ if(s[end] == ch){ break; } end--; } unordered_set tmp; start++; while(start < end){ tmp.insert(s[start]); start++; } cnt = cnt + tmp.size(); } return cnt; } };

[@_PRANAYMATE]

@@RUSTYYYYYYYYY Hey How are u doing in DSA now It is been 9 months

[@sourabhchoudhary-30]

Seriously, I found the same. You earned a subscriber MIK.

[@AyanSohail-oq7vk]

studying from an iit-k graduate for free on youtube i am so glad that he does this if he'll charge for it would be more than 30k a month to teach this.

[@gui-codes]

I think now, it would be 1 lac 😅. But thank god he teaches for free.

[@TEJASSURYA-r2v]

He is from IIEST Shibpur🔥

[@_PRANAYMATE]

Hi mik bhaiyya Solved on my own without being watched your video But later watched your video to see and understand the other aproaches told by you !! Feels Confident in Strings Now Thanks Bhaiyya Solution In Java with My Approach time taken 42ms Time Complexity O(n) space Complexity (2*26) that is constant public int countPalindromicSubsequence(String s) { boolean [] visited=new boolean[26]; boolean [] taken=new boolean[26]; int cnt=0; int i=0; int j=s.length()-1; while((ii && ch!=s.charAt(j)) { j--; } if(ch==s.charAt(j)) { for(int k=i+1;k

[@wearevacationuncoverers]

TRUST - "When you hope, MIK will upload both approaches and he really does". ❣

[@RV-qf1iz]

Thanks Bro, I was able to code it myself after understanding the approach.

[@codestorywithMIK]

Thank you for watching 😇❤️❤️

[@darkgaming2816]

nice solution

[@rahul_sharma546]

Underrated channel keep it up Why you only have 12k subscribers improve photos and show your face

[@codestorywithMIK]

Thank you Rahul. Really appreciate your kind words and precious suggestions 🙏❤️😇 Let me soon try to improve the thumbnail to get better ctr. Thank you again

[@mohammadaftabansari6882]

Thanks for the awesome explanation.

[@rashmipriya1073]

thank you sir ...your explanation is amazing.

[@dhairyachauhan6622]

thanks for explaining the time complexity, i was not able to figure out why it was working

[@codestorywithMIK]

Thank you 🙏❤️😇

[@GungunSaluja-sy6br]

nice explanation loved it!❤❤

[@codecraftV]

rightmost vale character ko isliye pakadna ye ki if choose for nextOcc then in first test case "aaa" will be missed , isliye choose last Occ of a char

[@codestorywithMIK]

Yep ❤️

[@dakshmalik14]

Thanks bro, first 10 minutes were enough to code it myself ❤

[@joydeep-halder]

Thank you bhaiya. Aj ka question ka intuition aa hi nhi rha tha.

[@aws_handles]

Just love your explanation and intuition building. Big fan of your work ❤

[@imPriyansh77]

Thank you bhaiya!!! This was an interesting problem.

[@gui-codes]

crystal clear MIK. you are the best sir.

[@DivyanshAggarwal-p1g]

brillient sir

[@sauravchandra10]

This was a tricky questions, thanks for the explanation.

[@codestorywithMIK]

Glad it was helpful!

[@rockykumarverma980]

Thank you so much bhaiya ji 🙏🙏🙏

[@sunnykumarpal5087]

Bhaiya ur way of teaching is fantastic . I enjoy learning from ur videos . I have a request for u bhaiya please can u make solution videos for leetcode contests.

[@codestorywithMIK]

Thanks a lot. I posted a video today - “Maximum XOR of two numbers” This will help to get understanding on last contest Qn-4 (Maximum Strong Pair COR II) Give it a try 😇🙏

[@aryansinha1818]

Dil se sukriya

[@DurgaShiva7574]

Aapke intuition ko salaam ❤❤

[@codestorywithMIK]

Means a lot 😇🙏❤️

[@8daudio672]

Thanks you sir !!

[@aamiramin6112]

Very nicely explained. Thanks for sharing

[@codestorywithMIK]

Thank you 🙏❤️😇

[@thefinalfit]

Masterpiece explanation as always sir 👌🏻👌🏻

[@Ramneet04]

Hi bhaiya can you make a video on Kmp algorithm. And please tell is it important? As i was doing and watched many vedio but didn't get it.Thankyou

[@codestorywithMIK]

Yes it’s important. Here it is - kzbin.info/www/bejne/p5LWlqZjbsyCps0si=WDpG81RfsXWdXUX1 😇❤️🙏

[@samreenjahan2482]

Loved the video. thanks for uploading🤩☺

[@codestorywithMIK]

Thank you for watching 😇🙏

[@FanIQQuiz]

I also thought that specifically asking 3 length palindrome, something is fishy. Thanks for making this easy

[@hemant_kumar_071]

Sir Please make a video on Line Sweep Algo

[@DevOpskagyaan]

Perfection = codestorywithMIK

[@THOSHI-cn6hg]

class Solution { public: int countPalindromicSubsequence(string s) { unordered_set letters; for (char c : s) { letters.insert(c); } int res = 0; for (char letter : letters) { int firstind = -1; int lastind = -1; for (int i = 0; i < s.size(); i++) { if (s[i] == letter) { if (firstind == -1) { firstind = i; } lastind = i; } } if (firstind != lastind ) { unordered_set middle; for (int i = firstind + 1; i < lastind; i++) { middle.insert(s[i]); } res += middle.size(); } } return res; } };

[@JoyAcharyatvl]

nice and awesome bhai

[@codestorywithMIK]

Thanks a lot 😇🙏

[@adityaojha4892]

for me 10:54 was the time, when my own intution and solution strike me

[@rupeshverma250]

bhai ek baat bole apka explanation and voice ek dam sooth hota hai bilkul makkhan ki taraha 🙂

[@codestorywithMIK]

Means a lot ❤️❤️🙏🙏🙏

[@nikhiltiwari20]

How the 2nd approach is o(1) If the last loop in the worst case run for o(N) and all are unique element inside that then it will add o(N) element which means the sc will be o(N) right? so overall tc and sc will be o(N) for the 2nd approach also.

[@codestorywithMIK]

Yes yes, it’s O(N) github.com/MAZHARMIK/Interview_DS_Algo/blob/master/strings/Unique%20Length-3%20Palindromic%20Subsequences.cpp

[@theOmKumar]

I did it like this. //first intuition brute: int countPalindromicSubsequence(string s) { unordered_set st; for(int i = 0; i < size(s); i++){ for(int j = i+1; j < size(s); j++){ for(int k = j+1; k < size(s); k++){ if (s[k] == s[i]){ string temp = s.substr(i,1) + s.substr(j,1) + s.substr(k,1); st.insert(temp); break; } } } } return st.size(); } # APPROACH 1 : by observation, push unique i,j & (i should be equal to k) int countPalindromicSubsequence(string s) { int count = 0; unordered_map mpi; for(int i = 0; i < size(s); i++){ if (mpi[s[i]]) continue; mpi[s[i]] = true; unordered_mapmpj; for(int j = i+1; j < size(s); j++){ if (mpj[s[j]]) continue; mpj[s[j]] = true; for(int k = j+1; k < size(s); k++){ if (s[k] == s[i]){ count++; break; } } } } return count; } //Approach 2: observation */ class Solution { public: int countPalindromicSubsequence(string s) { int count = 0; //char -> {start,end} unordered_map m; for(int i = 0; i < size(s); i++){ if (m.find(s[i]) == m.end()) m[s[i]] = {i,i}; else m[s[i]].second = i; } for(auto c : m){ int start = c.second.first; int end = c.second.second; unordered_set st; //push unique middle element in set for (int i = start+1; i < end; i++) st.insert(s[i]); count += st.size(); } return count ; } }; //Optimal

[@umeshbisht1054]

Thanku bhaiya ❤

[@codestorywithMIK]

Most welcome ❤️❤️

[@m_fi8926]

i know its a bit late. but feeling relaxed after completing

[@priyanshugouravsarangi8553]

Thought of dp first actually with all those subsequences and count ways in the question

[@codestorywithMIK]

Actually this indeed can be solved using DP but it would not be as optimal as this one - O(n)

[@priyanshugouravsarangi8553]

​@@codestorywithMIKthink it would be more like bitmasking or is there any other way

[@codestorywithMIK]

@priyanshugouravsarangi8553 Yes bit masking would be optimal dp most probably . Other ways can be to do a normal recursion+memoization (skip and take)

[@saurabhKumar-hj6yp]

Thanks

[@codestorywithMIK]

Most Welcome 🙏❤️😇

[@sukomal07]

so good

[@codestorywithMIK]

Thank you so much 🙏❤️

[@haris7247]

I tried this approach but it was failing for 1st test case while passed the rest of the 2. Pls tell me what am I doing wrong! class Solution { public: int countPalindromicSubsequence(string s) { int n = s.length(); unordered_set uniquePalindromes; for(int i=0; i

[@parthbhatti4151]

i was able to get the correct intuition but not in this much detail me intuition to soch ta hu left and right occurence wala but itni details me nhi soch pata

[@tutuimam3381]

❤❤❤❤❤❤❤

[@khushvantkumar1670]

why this is not solve by memoization(dp)

[@25-cse-csmohitkumarmandal59]

+1

[@rahiljakir]

Python Solution || 90% class Solution: count = 0 def countPalindromicSubsequence(self, s: str) -> int: unique = set(s) for u in unique: f = s.find(u) l = s.rfind(u) if (f != l): self.count += len(set(s[f+1:l])) return self.count

[@AkOp-bf9vm]

MY APPROACH:: T.C->O(N)+O(N*26) AND S.C->O(1) class Solution { public: int countPalindromicSubsequence(string s) { int n=s.size(); vector startIndex(26,-1); vector endIndex(26,0); int result=0; for(int i=0;i=0) endIndex[idx]=i; else startIndex[idx]=i; } for(int i=0;i

[@princejatav8456]

❤❤

[@challengeAceiver]

Bhaiya iss question ko mein ne dp se solve karne ka try karr rha hu just to understand the dp but mein apne code ko memorize nahi karr paa rha hu bohot try kiya but fir bhi nahi hua. Aap pls bata sakte ho ki ise memorize kaise karu? class Solution { public: set st; bool isPalindrome(string s){ return (s[0]== s[2])? true: false; } void solve(string &s, int ind, string &output){ if(ind== s.size()){ if(output.size()== 3 && isPalindrome(output)) st.insert(output); return; } solve(s, ind+ 1, output); output.push_back(s[ind]); solve(s, ind+ 1, output); output.pop_back(); } int countPalindromicSubsequence(string s) { string output; solve(s, 0, output); return st.size(); } };

[@unknown47896]

u cannot memoize this type

[@challengeAceiver]

@@unknown47896 but humein options dikhayi de to rahe hai to fir kyu nahi? and dp[ind][op.size()] aisa kuch nahi kar sakte?

[@unknown47896]

@@challengeAceiver ind and op.size() these two won't guarentee u a distinct state

[@soumyajitpaul-p8z]

Can anyone explain me how rightindex is working, if all the time we update rightindex then how do I know that left and right indies are same , it might be a _ b ,

[@gui-codes]

first_idx is updated only once when the character letter is encountered for the first time in the string. last_idx is updated every time the character letter is encountered, ensuring it holds the index of the last occurrence. These indices define the boundaries of the substring within which we check for unique characters (st) that could form the middle character of a palindrome. If the first and last occurrences of letter are the same (e.g., first_idx == last_idx), then the substring between them is empty. In this case, no valid palindromes of length 3 can be formed with letter as the first and last character.

[@unknown47896]

my O(NlogN) solution which is intuitive C++ CODE: class Solution { public: int countPalindromicSubsequence(string s) { int n=s.length(); unordered_set st; vector f(26,0); int ans=0; vector b(n,vector(26,0)); vector freq(26,0); for(int i=n-1;i>=0;i--) { int ind = s[i]-'a'; freq[ind]++; b[i]=freq; } for(int i=0;i

[@gdp1660]

I was trying this : Did not work anyways. Can anyone give a correct approach by this method? class Solution { public: bool isPalindrome(string temp){ int i = 0; int j = temp.size()-1; while(i

[@harshugamer7776]

//java code class Solution { public int countPalindromicSubsequence(String s) { int map[] = new int[26]; for(int i = 0 ; i < s.length() ; i++){ map[s.charAt(i) - 'a']++; } int count = 0; for(int i = 0 ; i < 26 ; i++){ if(map[i] > 1){ int left = leftmost(s, (char)(i + 'a')); int right = rightmost(s, (char)(i + 'a')); HashSet set = new HashSet(); for(int j = left + 1 ; j < right ; j++){ set.add(s.charAt(j)); } count += set.size(); } } return count; } public int leftmost(String s, char c){ for(int i = 0 ; i < s.length() ; i++){ if(s.charAt(i) == c) return i; } return -1; } public int rightmost(String s, char c){ for(int i = s.length() - 1 ; i >= 0 ; i--){ if(s.charAt(i) == c) return i; } return -1; } }

[@krunalkp1032]

I don't think this is o(n) solution it's o(n2) in worst case image string like abxxxxxxxxxxxxab we are repeating x in both case 2 times for a and b. I guess it should be o(n2)

[@xiaoshen194]

Why yellow theme in thumbnail? 👎

[@codestorywithMIK]

Hey, Actually i am currently experimenting which thumbnail gives more CTR . Will try more but definitely not this yellow one now as per your feedback. Thanks a lot for the valuable feedback always ❤️❤️❤️

[@dayashankarlakhotia4943]

public int countPalindromicSubsequence(String s){ int ans=0; int []first=new int[26], []last=new int[26]; Arrays.fill (first,s.length ()); for(int i=0;i

[@krunalkp1032]

And me dumbass solved this with backtracking by pick non pick method it went to 2^n worse than n^3 I have to think before directly jumping into the solution class Solution: def countPalindromicSubsequence(self, s: str) -> int: ip = s op = '' answer = [] s = set() count = 0 def solve(ip,op): nonlocal count if len(op) == 3: if op == op[::-1]: if op not in s: s.add(op) count += 1 return if not ip: return op1 = op + ip[0] op2 = op solve(ip[1:],op1) solve(ip[1:],op2) solve(ip,op) return count