Recursion Subset, Subsequence, String Questions
Vložit
- čas přidán 8. 07. 2024
- This is part 1 of the subset + string #recursion series. Here we cover some important tips to solve string recursion problems, along with subset patterns and how to convert recursive programs to iterative.
Take part in the learning in public initiative! Share your learnings on LinkedIn and Twitter with #DSAwithKunal & don't forget to tag us!
👉 Resources
- Join Replit: join.replit.com/kunal-kushwaha
- Complete Java DSA playlist: • Java + DSA + Interview...
- Code, Assignments, & Notes: github.com/kunal-kushwaha/DSA...
➡️ Connect with me: kunalkushwaha.com
=========================================
Timestamps:
0:00:00 Introduction
0:01:40 Basic String Questions using Recursion
0:02:19 Q1 : Skip a character
0:17:30 Q2 : Skip a string
0:21:32 Q3 : Skip a string if it's not the required string
0:24:34 Subsets Introduction
0:31:35 When to apply subset problem?
0:32:35 Q4 : Subsequences
0:43:11 Q5 : Return an ArrayList of string
0:52:10 Q6 : Print ASCII value of a character
0:54:15 Q7 : Subsequences with ASCII values
0:58:21 Q8 : Iterative program to print subsequences
1:09:48 Complexity Analysis
1:12:15 Q9 : Subsequences of a string with duplicate elements
1:22:07 Outro
#placement #dsa #interviews
Brother you are legend
Several videos I have seen but I never understood these concepts
You made these thing so easy
Thanks Brother for such a beautiful and lovely content
Concepts are fully cleared
With the help of these videos now I have the faith and confidence to crack good companies
Thanks Brother once again
Great going
Keep it up and deliver content like these
Thank You 🙏
@@KunalKushwaha at 1:16:50 we should not sort the array as it will rearrange the array and subsets will be wrong.
And we know in subset : 2, 1, 2 is the subset of 2, 1, 2 but 1, 2, 2 is not subset of 2, 1, 2
@@gouravsyal2052 yep bro
2,1,2 is subset of 2,1,2
@@KunalKushwaha sir it change order of array 2,1,2 while sort it become 1,2,2 1,2,2 is not subset of (2,1,2 ) .(2,1,2) is subset of 2,1,2 1:16:08
If someone had skills like you especially the way you teach, they would launch this course as a paid one. Let it be anyone in this world. But you're here trying to help students like me and I'm very grateful. Thanks a ton, Kunal!
Dont give him ideas!
I dreaded recursion subset problem for almost an year now, and I stopped practicing because I was not very good with recursion. Now I can re-begin and work my way to FAANG
me in the situation where i cant understand subset problems specially when for loop is used
@@jamtaranumber2841 you still struggling w/ iterative approach? lemme know, i can help you, can share the explanation here
@@sameerakhatoon9508 yeah can you share your discord / linkedin
Sister are u in good company now?
First I found Difficulty in understanding the subset problem . After carefully going through I too got it .This guy is awesome
No one taught me recursion like you. I, like many others like me, initially thought I understood recursion completely after watching the Fibonacci and Factorial examples. But then the reality hit when I tried to solve some medium-level problems. I realized that my concepts are so hazy that I had no clue how to apply anything I learnt in logically writing code to solve a problem. This site not only taught me the concept, but it is also so thorough that it forced me see what is happening from different angles and write code in multiple ways. Thanks, Kunal, for making recursion as clear as algebra instead of it being some monster like vector calculus or something. You are so thorough. Awesome.
Hello Kunal. I want to know, After the DSA course, will you show us how to use our skills in open source and all that stuffs till how to approach in a company? If not then please consider this.🙏🙏🙏
no one explained recursion in so much detail like Kunal. Please someone give Kunal a medal already
This is such a great video and it's incredible that you are not charging for sharing this immense knowledge.
Just love the way you first explain the approach ,how to think and then actually solve the problem.Thankyou so much for these videos .
And please please upload the graph and trees series 🙌
Amazing!!!! You proved that a good teacher is not one who tells all the solutions but someone we can lead us to all solutions. As once I listen to you logic coding has become damn easy!!
24:52 - 24:58 If I am not wrong, sliding window has not covered.
Don't worry he keeps track of syllabus on github issue, maybe mistakenly said that.
Bro when i see your video it gives me confidence 👍
Kunal, I cannot believe this is so easy. I wrapped my head around with backtracking a lot and was still confused. Even took sessions of a paid educational website to understand backtracking. And literally I just watched your video once and all concepts are clear.
You are legend.
+1
Hii can u please tell me that is this course worth following as m a beginner no programming background plz reply confused
@@manavarora7644 Hii can u please tell me that is this course worth following as m a beginner no programming background plz reply m confused
@@rishika9102 PICK A programming language first, then learn it.
In ques 9 we can just check if outer list contains that subset. If it doesn't contain, then only we should add it in outer. This way we'll avoid duplicates:
public static List subsetDuplicates(int[] arr)
{
List outer = new ArrayList();
outer.add(new ArrayList());
for(int num: arr)
{
int n= outer.size();
for (int i = 0; i < n; i++)
{
List inner=new ArrayList(outer.get(i));
inner.add(num);
if(!outer.contains(inner))
outer.add(inner);
}
}
return outer;
}
1:21:31 it will be good if we sort the array first, for the test cases like [1, 2,2,2] or [4, 4,4,1,4]. otherwise it will fail.
Great job man!
.contains will take another internal nested loop so it increases the time complexity...
@@kcalbduorp3499 yes
just started ur dsa course and fell in love with that
'Recursion made easy' by kunal.
Good Intuation, Thought process and superb way of teaching.
Good work 🙂
Q9 : Subsequences of a string with duplicate elements
Can be solved in easier way with the code snippet mentioned below:-
------------------------------------------------------
List outerList = new ArrayList();//outerList
outerList.add(new ArrayList());
for (int num : arr) {
int size = outerList.size();
for (int i = 0; i < size; i++) {
List internalList = new ArrayList(outerList.get(i));
internalList.add(num);
if (!outerList.contains(internalList)) {
outerList.add(internalList);
}
}
}
return outerList;
---------------------------------------------------------
contains method takes O(n) of time then it leads to O(n^3) for overall time complexity
static List subSetDuplicates(int[] nums) {
Arrays.sort(nums);
List outerList = new ArrayList();
outerList.add(new ArrayList());
for (int i = 0 ;i < nums.length ; i++) {
int start = 0;
int end = outerList.size();
if( i > 0 && nums[i] == nums[i - 1]){
start = start + (end - start ) / 2;
}
for (int j = start; j < end; j++) {
ArrayList intenalList = new ArrayList(outerList.get(j));
intenalList.add(nums[i]);
outerList.add(intenalList);
}
}
return outerList;
}
Everytime you make me like your video no matter what
I don't know anyone who explains every small things like you
I love that you made this beautiful course for free even though it's so much worth.
May krishna bless you !
difficult to understand iterative and duplicate problems :(
😢😢
Finally!!! I understood these topics... you r a legend kunall
you are genius man , i did the subset problem of string "abc" and i used loop inside that , and you simple printed using recursion 🙌
Insanely simple explanation of subsets... M awestruck
After all that your efforts and following all the previous playlist videos , Now i get some confidence in DSA to solve problems easily . Thanks Kunal bhaiyaa (Sir) for all that quality Content that i hunt for all over youtube
Thanks for teaching us like no one did till now!! One small request, please make lectures on dynamic programming as well!!
This video took me 8 hr to get completed but it all worth it. Thank you so much ❤
I find his sub sequence tutorials much informative and communication is superb.
Dhanyawad apka iss DSA course ke liye
I have been watching your videos for so long it's been very helpful to grow personally
Incredible course,
the concept which you tell us in the starting of the recursion is enough to solve this problem and the track the answer in the function body is the awesome way to hold the answer more then the in the arguments
This is the first time that i understood recursion in subsets after a lot of hunt for this material .Thanks a lot!
Glad to hear that!
it is unbelievable how easy you can solve recursion tasks after watching these videos. You really get told HOW to think. Thanks alot!
So nice of you
We are grateful to you for the knowledge you are providing for free🙏🙏
Waiting for your next DSA video
#DSAWithKunal❤
for the last question instead of adding the start or end index , if found duplicate just start the inner loop with outerarray size / 2 and it works fine
#include
using namespace std;
vector subsetrec(string main,string pro){
vector s;
if(main.empty()){
s.push_back(pro);
return s;
}
char ch = main[0];
vector s1 = subsetrec(main.substr(1),pro);
vector s2 = subsetrec(main.substr(1),pro+ch);
s.insert(s.end(),s1.begin(),s1.end());
s.insert(s.end(),s2.begin(),s2.end());
return s;
}
void subsetitr(){
vector v{1,2,3,3};
vector res;
res.push_back({ });
for(int i=0;i 0 && v[i] == v[i-1]) j= (n/2); // LOOK HERE
for(;j
Can you explain your thought process behind why it works ?
@@gnanaprakashm843 he is just removing duplicates bro , that's it.
@@laxminarayanakoyyana1753 I see I'll look into it. thanks 🙏
touched my heart as always
Thank you so much for explaining this beautifully. When can we expected videos for DP, graphs and trees?
Your confidence level is what makes you different from others. The best dsa course ever!
can anybody please tell in which video kunal has covered sliding window...
@@rockrk2519 he hasn't covered yet he definitely will
Another great video. Thanks for the good work Kunal. Wish you the very best!
Legendary way of teaching! Thanks brother
My pleasure!
The definition and recursion tree for subsets was very very great❤❤
Ye Kunal ka course bhot mast hai. Sab samaj aa gya
Brother you are legend i see the spirit in you to become s Minecraft stremer . You will achive great success as gamer.
very good video, i used to detest recursion kinda like it more than iteration now
I like the way you teach it is amazing that you are giving the tricks which person can apply to various types of questions. It's true even now i feal it is the best course for DSA out there on CZcams thanks for your valuable time and efforts for us.
It would be so good if this was a whole course of DSA i would really like to learn whole DSA from you if it is feasible Please provide dynamic programing videos too! people would love it.
Thanks for course and your efforts!
Really awesome way of teaching finally, thinking in the recursive way, |2^n sub set
Amazing content bro... Keep doing the good work..Lots of luck 🎉
Thanks for the great tutorial please continue the series
thank you so much kunal♥
ye kya ho raha dsa se main bore kyon nhi ho raha ye toh magic ho gya kunal bhai ,love you bhai aisa best content ke liye ab lag raha main sikh jaunga dsa
Wait kar rha tha iske liye....
This is just brilliant Brother, Keep doing it. Just waiting for the DP series, Please do it soon.
Nice video kunal. For the last question we can add a check before adding the inner list to the outer list, If the outer list already contains the inner list or not
Great Video! Very well explained! Great job Kunal, thank you very much!
You’re welcome
Best recursion series I have watched.Excellent explanation. Thanks Kunal
You are most welcome
Thank you brother
Finally I understood how to solve the subsets problem..
Thanks a lot brother.
You are doing great
More to come
Great work bro !! Keep it up and keep making such videos for others to learn!!
phele to dur se pair chu k parNaam bro 🙏🙏 DhanSuuu lecture Kunal bhai... Nobody teaches like you.. but plz complete krdo bhai playlist... 🙏🙏
You are a genius kunal 😊
He is really good!
Just Enjoying every moment ❤. Love it😊
This and the merge sort video are the only one I just can't get in my head.
you are the BEST !!
One of most awaited vidoe
for qn 9, please find my recursive solution below
approach: if we ignore the occuring of duplicates char means we ignore each of that duplicate char
public class Recursion{
public static void main(String[] args) {
System.out.println(subSetsWithDupInString("122", ""));
}
static ArrayList subSetsWithDupInString(String str, String ans){
if(str.isEmpty()){
ArrayList ls = new ArrayList();
ls.add(ans);
return ls;
}
char ch = str.charAt(0);
ArrayList left = new ArrayList();
ArrayList right = new ArrayList();
int i = 1;
while(i
great video bro, thank you so much!!
That was beautiful @kunal.
Easiest explanation of recursion in internet.
please continue the series
bro that was ammazing.
I thought to take half of outer list size as start index, but sooner realize what if multiple duplicate elements are coming, it will fail to survive that condition
recursion is still hard but you explained it well
Thanks bro all the concepts u deliver is so clear sir. pls make some vdos on windows sliding, two pointer approach too sir.
you killed it bro
Thank you so much ! I always had problems with these type of questions. I have better grasp on these topics now.
Thank you so much
Truely informative and lots of creativity in teaching...became friend without meeting you..
Bro this content is great. thanks for your effort
Just one question man how did you get this much knowledge
Other : How to solve a problem.
Le kunal : How to approach a problem.
That was the plan
Thanks a lot
bro you're awesome thanks for the concepts you have taught us.👑👑👑
Bro, why I am getting error at p:p+ch, saying as Syntax error on token " : ", invalid AssignmentOperator.
Excellent!
pls kunal complete the course no other course can match the level of content u were providing
Mad respect
please schedule one orientation meeting for maitians ❤️ I'm also from mait cse
you are idol for lots of us 🙏🙏🙏
Thank you :)
Recursion session... Just like therapy session
thankyou for this course ...please upload more videossssss😭😭
00:03 String Questions and Subsequences
03:35 Recursion subset and subsequence concepts
10:19 Explanation of function call and process in string operations.
13:46 Recursion and string processing explained
21:02 Understanding recursion and string questions
24:31 Subset, subsequence, and string questions are important for interview preparation.
31:26 Understanding recursion and subset/sequence problems.
34:43 Recursion and string questions in a CZcams video
40:49 Discussion on various functions and activities using code
44:06 Recursion and string questions are challenging.
51:15 The video discusses creating subsequence and string questions.
54:30 Sequencing, string manipulation, and recursion in programming
1:01:07 Explaining recursion and its use in solving problems
1:04:05 Creating a new list based on the original list size.
1:10:16 Understanding subsets and complexities
1:13:16 Preventing duplicate elements in newly created subjects
" Take it and ignore it " 🙌
Please make a video on subarray concepts
In this example, the recursiveSubstring method prints the current substring and then makes a recursive call with s.substring(1). Each recursive call creates a new substring starting from the second character of the previous substring.
Output:
vbnet
Copy code
Substring: abcdef
Substring: bcdef
Substring: cdef
Substring: def
Substring: ef
Substring: f
Empty String
Kunal, please try completing the series. It'd be of great help. cuz of all the videos I've watched on recursion, all of them were very specific to the prlms they taught and none of them explained how recursion actually works. I don't think they'd do any better with topics like dp. So, if you can, complete the series
Waa ye hi time mila tha upload karne ko 😐
You are the best !!! please make some video about DP thanks ahead!!!
A new episode of recussion session 😂😂
hi Kunal can you please do sliding window problems?
Video 32 Completed!
Bhaiya i am getting admsion into DTU CS can u please make a video 1st year roadmap
I was waiting to get into college to start programming with ur course
Loving ur confidence and content
czcams.com/play/PLPX75d4curILdTmhcM5iJ6ReNx-LKW12P.html
here, these are old videos of kunal when he used to work with a ed-tech, he has made a complete 4 year roadmap for B.Tech students
U r diamond dude...May lord protect u from Aliens for the boon of mankind.
@Kunal Kushwaha
, the solution in Q9 changes the order of the original array. Wouldn't the result be considered as a list of subsets and not a list of subsequences?
Bhaiii you are legend, when you are coming with OOP java tutorials
Hi Kunal, thank you so much for the content! Do you know where I can find Dynamic Programming playlist? I couldn't find it anywhere on your channel. Thanks again brother