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
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.
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
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
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.
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 😇🙏
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.
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
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
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
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
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 ,
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.
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
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(); } };
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)
//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; } }
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 ❤️❤️❤️
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
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
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
So glad to hear. Thank you so much 😇🙏❤️
same maine bhi kiya par c++ me
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;
}
};
@@RUSTYYYYYYYYY Hey How are u doing in DSA now It is been 9 months
Seriously, I found the same. You earned a subscriber MIK.
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.
I think now, it would be 1 lac 😅. But thank god he teaches for free.
He is from IIEST Shibpur🔥
TRUST - "When you hope, MIK will upload both approaches and he really does". ❣
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
Yep ❤️
Thanks Bro, I was able to code it myself after understanding the approach.
Thank you for watching 😇❤️❤️
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
nice solution
Thanks for the awesome explanation.
thank you sir ...your explanation is amazing.
thanks for explaining the time complexity, i was not able to figure out why it was working
Thank you 🙏❤️😇
Thanks bro, first 10 minutes were enough to code it myself ❤
Underrated channel keep it up
Why you only have 12k subscribers improve photos and show your face
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
Thank you bhaiya. Aj ka question ka intuition aa hi nhi rha tha.
Thank you bhaiya!!! This was an interesting problem.
for me 10:54 was the time, when my own intution and solution strike me
Dil se sukriya
crystal clear MIK. you are the best sir.
Perfection = codestorywithMIK
Thanks you sir !!
Aapke intuition ko salaam ❤❤
Means a lot 😇🙏❤️
This was a tricky questions, thanks for the explanation.
Glad it was helpful!
nice explanation loved it!❤❤
Just love your explanation and intuition building. Big fan of your work ❤
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.
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 😇🙏
Very nicely explained. Thanks for sharing
Thank you 🙏❤️😇
I also thought that specifically asking 3 length palindrome, something is fishy. Thanks for making this easy
brillient sir
Thank you so much bhaiya ji 🙏🙏🙏
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
Yes it’s important.
Here it is - ua-cam.com/video/qases-9gOpk/v-deo.htmlsi=WDpG81RfsXWdXUX1
😇❤️🙏
Masterpiece explanation as always sir 👌🏻👌🏻
i know its a bit late. but feeling relaxed after completing
Sir Please make a video on Line Sweep Algo
Loved the video. thanks for uploading🤩☺
Thank you for watching 😇🙏
nice and awesome bhai
Thanks a lot 😇🙏
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;
}
};
bhai ek baat bole apka explanation and voice ek dam sooth hota hai bilkul makkhan ki taraha 🙂
Means a lot ❤️❤️🙏🙏🙏
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
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.
Yes yes, it’s O(N)
github.com/MAZHARMIK/Interview_DS_Algo/blob/master/strings/Unique%20Length-3%20Palindromic%20Subsequences.cpp
Thanku bhaiya ❤
Most welcome ❤️❤️
Thought of dp first actually with all those subsequences and count ways in the question
Actually this indeed can be solved using DP but it would not be as optimal as this one - O(n)
@@codestorywithMIKthink it would be more like bitmasking or is there any other way
@priyanshugouravsarangi8553 Yes bit masking would be optimal dp most probably .
Other ways can be to do a normal recursion+memoization (skip and take)
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
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
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
so good
Thank you so much 🙏❤️
Thanks
Most Welcome 🙏❤️😇
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
why this is not solve by memoization(dp)
+1
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
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 ,
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.
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
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();
}
};
u cannot memoize this type
@@unknown47896 but humein options dikhayi de to rahe hai to fir kyu nahi? and dp[ind][op.size()] aisa kuch nahi kar sakte?
@@challengeAceiver ind and op.size() these two won't guarentee u a distinct state
❤❤❤❤❤❤❤
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)
//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;
}
}
Why yellow theme in thumbnail? 👎
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 ❤️❤️❤️
❤❤
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
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