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 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
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
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
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
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.
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
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)
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(); } };
//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; } }
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
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 ❤️❤️❤️
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.
nice solution
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🔥
Thanks for the awesome explanation.
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 😇❤️❤️
thank you sir ...your explanation is amazing.
TRUST - "When you hope, MIK will upload both approaches and he really does". ❣
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
Thanks bro, first 10 minutes were enough to code it myself ❤
Just love your explanation and intuition building. Big fan of your work ❤
Thank you bhaiya!!! This was an interesting problem.
crystal clear MIK. you are the best sir.
nice explanation loved it!❤❤
Thank you so much bhaiya ji 🙏🙏🙏
thanks for explaining the time complexity, i was not able to figure out why it was working
Thank you 🙏❤️😇
brillient sir
for me 10:54 was the time, when my own intution and solution strike me
Thank you bhaiya. Aj ka question ka intuition aa hi nhi rha tha.
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
Aapke intuition ko salaam ❤❤
Means a lot 😇🙏❤️
Dil se sukriya
This was a tricky questions, thanks for the explanation.
Glad it was helpful!
Loved the video. thanks for uploading🤩☺
Thank you for watching 😇🙏
Very nicely explained. Thanks for sharing
Thank you 🙏❤️😇
Masterpiece explanation as always sir 👌🏻👌🏻
i know its a bit late. but feeling relaxed after completing
Perfection = codestorywithMIK
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 😇🙏
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 - ruclips.net/video/qases-9gOpk/видео.htmlsi=WDpG81RfsXWdXUX1
😇❤️🙏
Sir Please make a video on Line Sweep Algo
I also thought that specifically asking 3 length palindrome, something is fishy. Thanks for making this easy
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;
}
};
nice and awesome bhai
Thanks a lot 😇🙏
Thanku bhaiya ❤
Most welcome ❤️❤️
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
bhai ek baat bole apka explanation and voice ek dam sooth hota hai bilkul makkhan ki taraha 🙂
Means a lot ❤️❤️🙏🙏🙏
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
so good
Thank you so much 🙏❤️
Thanks
Most Welcome 🙏❤️😇
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
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 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
❤❤❤❤❤❤❤
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
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
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.
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
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)
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
❤❤
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
//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;
}
}
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
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 ❤️❤️❤️
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