title

Dp 25. Longest Common Subsequence | Top Down | Bottom-Up | Space Optimised | DP on Strings

description

Lecture Notes/C++/Java Codes: https://takeuforward.org/dynamic-programming/striver-dp-series-dynamic-programming-problems/
Problem Link: https://bit.ly/3pvkqUd
Pre-req for this Series: https://www.youtube.com/watch?v=yVdKa8dnKiE&list=PLgUwDviBIf0rGlzIn_7rsaR2FQ5e6ZOL9
a
Make sure to join our telegram group for discussions: https://linktr.ee/takeUforward
Full Playlist: https://www.youtube.com/watch?v=FfXoiwwnxFw&list=PLgUwDviBIf0qUlt5H_kiKYaNSqJ81PMMY
In this video, we solve the LCS Dp, this is the first problem on the pattern Strings on DP.
If you have not yet checked our SDE sheet, you should definitely do it: https://takeuforward.org/interviews/strivers-sde-sheet-top-coding-interview-problems/
You can also get in touch with me at my social handles: https://linktr.ee/takeUforward

detail

{'title': 'Dp 25. Longest Common Subsequence | Top Down | Bottom-Up | Space Optimised | DP on Strings', 'heatmap': [{'end': 2266.341, 'start': 2231.567, 'weight': 1}], 'summary': 'Tutorial on dynamic programming (dp) covers topics related to dp on strings, longest common subsequence, finding longest common subsequences, state repetition in lcs algorithm, applying memory action, debugging techniques, tabulation, dp index shifting, and space optimization, providing comprehensive understanding and examples for mastery in solving dp on strings problems.', 'chapters': [{'end': 82.885, 'segs': [{'end': 82.885, 'src': 'embed', 'start': 24.013, 'weight': 0, 'content': [{'end': 28.94, 'text': 'And again, when we complete dp on strings, you can solve any problem on dp on strings.', 'start': 24.013, 'duration': 4.927}, {'end': 29.962, 'text': "That's my guarantee.", 'start': 28.98, 'duration': 0.982}, {'end': 36.165, 'text': "So, to start off with, Let's take the first problem, which is longest common subsequence.", 'start': 30.382, 'duration': 5.783}, {'end': 41.647, 'text': "Yes But if you're understanding that, let's understand this term subsequence in depth.", 'start': 36.625, 'duration': 5.022}, {'end': 47.389, 'text': 'What is subsequence? So if I write ABC, A is a subsequence.', 'start': 42.087, 'duration': 5.302}, {'end': 49.009, 'text': 'B is a subsequence.', 'start': 48.129, 'duration': 0.88}, {'end': 49.869, 'text': 'C is a subsequence.', 'start': 49.029, 'duration': 0.84}, {'end': 50.89, 'text': 'AB is a subsequence.', 'start': 49.99, 'duration': 0.9}, {'end': 51.91, 'text': 'BC is a subsequence.', 'start': 50.91, 'duration': 1}, {'end': 52.91, 'text': 'AC is a subsequence.', 'start': 52.01, 'duration': 0.9}, {'end': 54.491, 'text': 'ABC is a subsequence.', 'start': 53.391, 'duration': 1.1}, {'end': 57.632, 'text': 'MT string is also a subsequence.', 'start': 55.171, 'duration': 2.461}, {'end': 72.261, 'text': 'What is a subsequence in a string S? You see BC, repetitive BC is consecutive and maintaining the order of B and C, maintaining the order of B and C.', 'start': 58.552, 'duration': 13.709}, {'end': 77.603, 'text': 'You see AC, AC is not consecutive but maintaining the order of AC.', 'start': 72.261, 'duration': 5.342}, {'end': 82.885, 'text': 'ABC is consecutive and maintaining the order, very simple.', 'start': 78.443, 'duration': 4.442}], 'summary': 'Understanding subsequence in strings is crucial for solving dp problems.', 'duration': 58.872, 'max_score': 24.013, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/NPZn9jBrX8U/pics/NPZn9jBrX8U24013.jpg'}], 'start': 0.339, 'title': 'Dp on strings', 'summary': "Introduces dynamic programming (dp) on strings, emphasizing solving comparison, replacements, and edits, ensuring mastery for solving any dp on strings problem. it explores subsequences using the example of string 'abc' and its various combinations.", 'chapters': [{'end': 82.885, 'start': 0.339, 'title': 'Dp on strings: understanding subsequences', 'summary': "Introduces dynamic programming (dp) on strings, focusing on solving problems related to comparison, replacements, and edits, with a guarantee that mastering this pattern will enable solving any dp on strings problem. it delves into the concept of subsequences using the example of string 'abc' and its various subsequence combinations.", 'duration': 82.546, 'highlights': ['The chapter guarantees that mastering DP on strings will enable solving any problem related to this pattern.', "The chapter introduces the concept of subsequences using the example of string 'ABC', explaining the different subsequence combinations such as A, B, C, AB, BC, AC, and ABC.", 'DP on strings involves solving problems related to comparison, replacements, and edits.']}], 'duration': 82.546, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/NPZn9jBrX8U/pics/NPZn9jBrX8U339.jpg', 'highlights': ['The chapter guarantees that mastering DP on strings will enable solving any problem related to this pattern.', 'DP on strings involves solving problems related to comparison, replacements, and edits.', "The chapter introduces the concept of subsequences using the example of string 'ABC', explaining the different subsequence combinations such as A, B, C, AB, BC, AC, and ABC."]}, {'end': 449.341, 'segs': [{'end': 136.019, 'src': 'embed', 'start': 84.676, 'weight': 0, 'content': [{'end': 86.477, 'text': 'can be consecutive.', 'start': 84.676, 'duration': 1.801}, {'end': 100.321, 'text': 'it cannot be consecutive, but as long as it maintains the order, maintains the order in the string, then you can call it as a subsequence.', 'start': 86.477, 'duration': 13.844}, {'end': 106.983, 'text': 'right, and in order to print all these subsequences, you might be thinking striver.', 'start': 100.321, 'duration': 6.662}, {'end': 109.184, 'text': 'how do i print all the subsequences?', 'start': 106.983, 'duration': 2.201}, {'end': 120.949, 'text': 'so in order to print all the subsequences, you can use Either power set I have a video on this or you can use the recursion method again.', 'start': 109.184, 'duration': 11.765}, {'end': 124.331, 'text': 'I have a video on both of them and if you watch the video,', 'start': 120.949, 'duration': 3.382}, {'end': 131.935, 'text': 'for any given string like this string is of a length 3 and the number of subsequences is 8..', 'start': 124.331, 'duration': 7.604}, {'end': 136.019, 'text': 'including the empty one where i say i do not pick anyone.', 'start': 131.935, 'duration': 4.084}], 'summary': 'To print all subsequences of a string, use power set or recursion. a string of length 3 has 8 subsequences.', 'duration': 51.343, 'max_score': 84.676, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/NPZn9jBrX8U/pics/NPZn9jBrX8U84676.jpg'}], 'start': 84.676, 'title': 'Longest common subsequence', 'summary': 'Explains subsequences, their count, and printing method. it also introduces the concept of longest common subsequence and its significance, with an example of 32 subsequences for a string of length 5. additionally, it discusses finding the longest common subsequence in two given strings, drawbacks of brute force approach, and exploring the alternative of using recursion with parameters to generate subsequences.', 'chapters': [{'end': 235.318, 'start': 84.676, 'title': 'Understanding subsequences and longest common subsequence', 'summary': 'Explains the concept of subsequences, their count, and the method to print them, while also introducing the concept of longest common subsequence and its significance, with an example of 32 subsequences for a string of length 5.', 'duration': 150.642, 'highlights': ['The number of subsequences for a string of length n is 2 to the power n, including the empty one, where no elements are picked.', 'Longest common subsequence involves finding the common elements in two given subsequences, with an example of finding common subsequences for two strings that can each generate 32 subsequences.', 'The chapter introduces the concept of subsequences and explains that for a string of length 3, the number of subsequences is 8, including the empty one.']}, {'end': 449.341, 'start': 235.318, 'title': 'Finding longest common subsequence', 'summary': 'Explains the process of finding the longest common subsequence in two given strings and discusses the drawbacks of applying brute force and the approach of generating all subsequences and comparing them, highlighting the exponential time complexity, and explores the alternative of using recursion with parameters to generate subsequences.', 'duration': 214.023, 'highlights': ['Brute force method of generating all subsequences and linear comparison has exponential time complexity of 2 to the power n.', 'Exploration of the alternative approach of using recursion with parameters to generate subsequences instead of brute force method.', 'Demonstration of the application of recursion to find the longest common subsequence in given strings, ACD and CED.']}], 'duration': 364.665, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/NPZn9jBrX8U/pics/NPZn9jBrX8U84676.jpg', 'highlights': ['The number of subsequences for a string of length n is 2 to the power n, including the empty one, where no elements are picked.', 'Longest common subsequence involves finding the common elements in two given subsequences, with an example of finding common subsequences for two strings that can each generate 32 subsequences.', 'The chapter introduces the concept of subsequences and explains that for a string of length 3, the number of subsequences is 8, including the empty one.', 'Brute force method of generating all subsequences and linear comparison has exponential time complexity of 2 to the power n.', 'Exploration of the alternative approach of using recursion with parameters to generate subsequences instead of brute force method.', 'Demonstration of the application of recursion to find the longest common subsequence in given strings, ACD and CED.']}, {'end': 1359.322, 'segs': [{'end': 478.947, 'src': 'embed', 'start': 449.341, 'weight': 3, 'content': [{'end': 453.743, 'text': 'express everything in terms of indexes.', 'start': 449.341, 'duration': 4.402}, {'end': 458.314, 'text': 'explode, possibility on that index.', 'start': 453.743, 'duration': 4.571}, {'end': 459.355, 'text': "that's it.", 'start': 458.314, 'duration': 1.041}, {'end': 464.738, 'text': 'explore possibility on that index is what we do.', 'start': 459.355, 'duration': 5.383}, {'end': 469.321, 'text': "take the best among them, because you're looking for longest.", 'start': 464.738, 'duration': 4.583}, {'end': 472.083, 'text': 'take the best among them.', 'start': 469.321, 'duration': 2.762}, {'end': 475.345, 'text': 'these are the three rules that you generally follow.', 'start': 472.083, 'duration': 3.262}, {'end': 478.947, 'text': 'now, express everything in terms of index.', 'start': 475.345, 'duration': 3.602}], 'summary': 'Exploring possibilities based on indexes to find the best option.', 'duration': 29.606, 'max_score': 449.341, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/NPZn9jBrX8U/pics/NPZn9jBrX8U449341.jpg'}, {'end': 596.071, 'src': 'embed', 'start': 513.695, 'weight': 0, 'content': [{'end': 518.499, 'text': 'a single index cannot express both the strings.', 'start': 513.695, 'duration': 4.804}, {'end': 522.842, 'text': 'a single index cannot express both the strings.', 'start': 518.499, 'duration': 4.343}, {'end': 528.027, 'text': 'thereby I will have to represent them by two indexes.', 'start': 522.842, 'duration': 5.185}, {'end': 531.13, 'text': 'I have to represent them by two indexes.', 'start': 528.027, 'duration': 3.103}, {'end': 538.98, 'text': 'where index 1 represents this guy, index 2 represents this guy.', 'start': 531.13, 'duration': 7.85}, {'end': 542.166, 'text': "that's the first modification that you have to do in the rules.", 'start': 538.98, 'duration': 3.186}, {'end': 549.172, 'text': 'Since you are dealing with couple of strings, you express them in terms of index 1 and index 2..', 'start': 543.089, 'duration': 6.083}, {'end': 553.674, 'text': 'Very simple, like in all the array problems, you express everything in terms of index.', 'start': 549.172, 'duration': 4.502}, {'end': 559.277, 'text': 'Because there was an index, then you decided to pick, not pick or similar kind of things you did.', 'start': 554.495, 'duration': 4.782}, {'end': 564.319, 'text': 'Over here, we will have index 1 and index 2, which will be representing.', 'start': 559.837, 'duration': 4.482}, {'end': 575.887, 'text': "So can I say, if I omit this, i write this something as f of 2 comma 2, or rather, let's write it in a smaller way, f of 2 comma 2.", 'start': 564.66, 'duration': 11.227}, {'end': 577.627, 'text': 'what does this represent?', 'start': 575.887, 'duration': 1.74}, {'end': 588.149, 'text': 'tell me the lcs of string 0 to 2, string 1, 0 to 2 and string 2, 0 to 2.', 'start': 577.627, 'duration': 10.522}, {'end': 591.47, 'text': 'this is what this f of 2, 2 will represent.', 'start': 588.149, 'duration': 3.321}, {'end': 594.03, 'text': 'so we have understood the expressing term.', 'start': 591.47, 'duration': 2.56}, {'end': 595.571, 'text': 'we have understood the expressing term.', 'start': 594.03, 'duration': 1.541}, {'end': 596.071, 'text': "that's done.", 'start': 595.571, 'duration': 0.5}], 'summary': 'Two indexes needed to represent strings, like in all array problems.', 'duration': 82.376, 'max_score': 513.695, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/NPZn9jBrX8U/pics/NPZn9jBrX8U513695.jpg'}, {'end': 726.57, 'src': 'embed', 'start': 699.974, 'weight': 1, 'content': [{'end': 703.796, 'text': 'I got a subsequence of length 1, that is d, which is common in both of them.', 'start': 699.974, 'duration': 3.822}, {'end': 704.577, 'text': 'Again, makes sense.', 'start': 703.996, 'duration': 0.581}, {'end': 712.241, 'text': 'Thereby, I can probably say one of the possibilities that I can have is, I got one subsequence of length.', 'start': 705.157, 'duration': 7.084}, {'end': 715.222, 'text': 'and then i shrink the string.', 'start': 712.981, 'duration': 2.241}, {'end': 724.348, 'text': 'then i shrink the string and say the new string is ac and ce, in which probably you can find an answer in which you can probably find an answer.', 'start': 715.222, 'duration': 9.126}, {'end': 726.57, 'text': 'so does that make sense?', 'start': 724.348, 'duration': 2.222}], 'summary': "Found common subsequence 'd' of length 1 in both strings.", 'duration': 26.596, 'max_score': 699.974, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/NPZn9jBrX8U/pics/NPZn9jBrX8U699974.jpg'}, {'end': 1014.889, 'src': 'embed', 'start': 986.878, 'weight': 5, 'content': [{'end': 992.181, 'text': "And since they're not matching, the answer added to the longest will be 0.", 'start': 986.878, 'duration': 5.303}, {'end': 997.524, 'text': "Okay Make sense? I'll be like, that does make sense because I'll just move this index.", 'start': 992.181, 'duration': 5.343}, {'end': 1001.646, 'text': "I'll keep it because this guy might match in future with these guys.", 'start': 997.844, 'duration': 3.802}, {'end': 1006.449, 'text': "Okay But then you'll miss out on the C.", 'start': 1002.187, 'duration': 4.262}, {'end': 1007.69, 'text': "Okay Let's take the other way as well.", 'start': 1006.449, 'duration': 1.241}, {'end': 1012.585, 'text': "When I say, okay, listen, let's keep EC.", 'start': 1009.5, 'duration': 3.085}, {'end': 1014.889, 'text': "That means let's keep index one.", 'start': 1013.267, 'duration': 1.622}], 'summary': 'The answer added to the longest will be 0, making sense to move the index, potentially missing out on the c.', 'duration': 28.011, 'max_score': 986.878, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/NPZn9jBrX8U/pics/NPZn9jBrX8U986878.jpg'}], 'start': 449.341, 'title': 'Finding longest common subsequences', 'summary': "Focuses on expressing strings in terms of indexes, utilizing two indexes to represent different strings and understanding the concept of 'f of 2, 2' to find the longest common subsequence of given strings. it also explains the concept of finding the longest common subsequence between two strings, exploring all possibilities for matching and non-matching characters. additionally, it covers the process of comparing c and e in a string, exploring both possibilities and applying dynamic programming to find the maximum matching answer considering different scenarios and indexes. the chapter also explains the concept of dynamic programming and its application in finding the longest common subsequence in a string, highlighting the base case and possibilities, and emphasizing the significance of negative values as the end of the string.", 'chapters': [{'end': 596.071, 'start': 449.341, 'title': 'Expressing strings with indexes', 'summary': "Focuses on expressing strings in terms of indexes, utilizing two indexes to represent different strings and understanding the concept of 'f of 2, 2' to find the longest common subsequence of given strings.", 'duration': 146.73, 'highlights': ['The concept of expressing strings in terms of indexes and utilizing two indexes to represent different strings is emphasized as a fundamental rule.', "Understanding the 'f of 2, 2' representation to find the longest common subsequence of given strings is a key concept in the chapter.", 'The importance of expressing everything in terms of indexes and exploring possibilities based on the index is highlighted as a fundamental approach.']}, {'end': 882.792, 'start': 597.951, 'title': 'Longest common subsequence', 'summary': 'Explains the concept of finding the longest common subsequence between two strings, exploring all possibilities for matching and non-matching characters, with an emphasis on index comparisons and string shrinking.', 'duration': 284.841, 'highlights': ['The concept of finding the longest common subsequence between two strings is explained, with an emphasis on comparing characters at specific indices and shrinking the strings.', 'Exploring all possibilities for matching and non-matching characters is highlighted, emphasizing the importance of thorough examination to avoid issues.', 'The process of comparing characters at specific indices to determine matching and non-matching scenarios is detailed, along with the implications for the length of subsequences and string shrinking.']}, {'end': 1152.31, 'start': 882.792, 'title': 'Comparing c and e', 'summary': 'Explains the process of comparing c and e in a string, exploring both possibilities and applying dynamic programming to find the maximum matching answer considering different scenarios and indexes.', 'duration': 269.518, 'highlights': ['Exploring both possibilities of moving indexes 1 and 2 to find the maximum matching answer.', 'Applying dynamic programming to consider different scenarios and indexes for finding the maximum matching answer.', 'Considering the best option among all possibilities for matching C and E in the string.']}, {'end': 1359.322, 'start': 1152.31, 'title': 'Dynamic programming explained', 'summary': 'Explains the concept of dynamic programming and its application in finding the longest common subsequence in a string, highlighting the base case and possibilities, and emphasizing the significance of negative values as the end of the string.', 'duration': 207.012, 'highlights': ['The chapter explains the concept of dynamic programming and its application in finding the longest common subsequence in a string.', 'Highlighting the base case and possibilities.', 'Emphasizing the significance of negative values as the end of the string.']}], 'duration': 909.981, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/NPZn9jBrX8U/pics/NPZn9jBrX8U449341.jpg', 'highlights': ["Understanding the 'f of 2, 2' representation to find the longest common subsequence of given strings is a key concept in the chapter.", 'The concept of expressing strings in terms of indexes and utilizing two indexes to represent different strings is emphasized as a fundamental rule.', 'The concept of finding the longest common subsequence between two strings is explained, with an emphasis on comparing characters at specific indices and shrinking the strings.', 'Applying dynamic programming to consider different scenarios and indexes for finding the maximum matching answer.', 'Exploring all possibilities for matching and non-matching characters is highlighted, emphasizing the importance of thorough examination to avoid issues.', 'The chapter explains the concept of dynamic programming and its application in finding the longest common subsequence in a string.']}, {'end': 1737.369, 'segs': [{'end': 1415.275, 'src': 'embed', 'start': 1387.249, 'weight': 0, 'content': [{'end': 1391.549, 'text': 'this is how the recursive code will look like now.', 'start': 1387.249, 'duration': 4.3}, {'end': 1399.291, 'text': "in order to get more clarity, what I'll do is I'll take this example and try to do a recursion tree so that it gets clear on you,", 'start': 1391.549, 'duration': 7.742}, {'end': 1401.091, 'text': 'like on a crystal clear method.', 'start': 1399.291, 'duration': 1.8}, {'end': 1402.951, 'text': 'CED okay, where are we?', 'start': 1401.091, 'duration': 1.86}, {'end': 1403.692, 'text': 'we were here.', 'start': 1402.951, 'duration': 0.741}, {'end': 1404.372, 'text': 'we were here.', 'start': 1403.692, 'duration': 0.68}, {'end': 1406.312, 'text': 'okay, what did the first step?', 'start': 1404.372, 'duration': 1.94}, {'end': 1407.112, 'text': 'what will the first step be?', 'start': 1406.312, 'duration': 0.8}, {'end': 1412.793, 'text': "1 plus perfect, and we'll call the function so over here.", 'start': 1407.112, 'duration': 5.681}, {'end': 1415.275, 'text': 'it will be something like 0, 1, 2, 0, 1, 2.', 'start': 1412.793, 'duration': 2.482}], 'summary': 'A recursive code example is explained, with a plan to create a recursion tree for clarity.', 'duration': 28.026, 'max_score': 1387.249, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/NPZn9jBrX8U/pics/NPZn9jBrX8U1387249.jpg'}, {'end': 1669.407, 'src': 'embed', 'start': 1642.434, 'weight': 2, 'content': [{'end': 1645.657, 'text': 'straightforward in all the comparison of string problems.', 'start': 1642.434, 'duration': 3.223}, {'end': 1653.602, 'text': "if they're matching, you just take both of them back, and if they're not matching, you take either one string, you shrink one string,", 'start': 1645.657, 'duration': 7.945}, {'end': 1662.489, 'text': "or you shrink the other string and try to do a comparison, and if you're able to do this, you can actually solve any problem on string comparisons.", 'start': 1653.602, 'duration': 8.887}, {'end': 1666.132, 'text': 'if you can understand the movement of strings, fine enough.', 'start': 1662.489, 'duration': 3.643}, {'end': 1668.427, 'text': 'so what are we doing?', 'start': 1666.132, 'duration': 2.295}, {'end': 1669.407, 'text': 'as of now?', 'start': 1668.427, 'duration': 0.98}], 'summary': 'Strategies for solving string comparison problems by manipulating strings for efficient comparisons and problem-solving.', 'duration': 26.973, 'max_score': 1642.434, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/NPZn9jBrX8U/pics/NPZn9jBrX8U1642434.jpg'}], 'start': 1361.181, 'title': 'Longest common subsequence', 'summary': "Discusses the process of finding the longest common subsequence in a string using recursion and dynamic programming, highlighting the exponential time complexity and the need for optimization through memoization, ultimately leading to the identification of the longest common subsequence as 'cd'.", 'chapters': [{'end': 1737.369, 'start': 1361.181, 'title': 'Longest common subsequence', 'summary': "Discusses the process of finding the longest common subsequence in a string using recursion and dynamic programming, highlighting the exponential time complexity and the need for optimization through memoization, ultimately leading to the identification of the longest common subsequence as 'cd'.", 'duration': 376.188, 'highlights': ["The recursive approach to finding the longest common subsequence is demonstrated, showcasing the branching of function calls and the identification of the longest common subsequence 'CD'.", 'The exponential time complexity of the recursive approach is highlighted, with 2 to the power of n subsequences being generated for both strings, emphasizing the need for optimization.', 'The importance of optimizing the algorithm through memoization is emphasized, with the potential for applying memoization to address overlapping subproblems, thereby improving the efficiency of the solution.']}], 'duration': 376.188, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/NPZn9jBrX8U/pics/NPZn9jBrX8U1361181.jpg', 'highlights': ['The importance of optimizing the algorithm through memoization is emphasized, with the potential for applying memoization to address overlapping subproblems, thereby improving the efficiency of the solution.', "The recursive approach to finding the longest common subsequence is demonstrated, showcasing the branching of function calls and the identification of the longest common subsequence 'CD'.", 'The exponential time complexity of the recursive approach is highlighted, with 2 to the power of n subsequences being generated for both strings, emphasizing the need for optimization.']}, {'end': 1964.719, 'segs': [{'end': 1794.931, 'src': 'embed', 'start': 1763.101, 'weight': 1, 'content': [{'end': 1763.621, 'text': "that's okay.", 'start': 1763.101, 'duration': 0.52}, {'end': 1764.842, 'text': 'but you will see.', 'start': 1763.621, 'duration': 1.221}, {'end': 1768.385, 'text': 'if you take a bigger example, you will see states being repeated.', 'start': 1764.842, 'duration': 3.543}, {'end': 1773.43, 'text': "you can take a bigger set of string and you'll see that the states are repeated.", 'start': 1768.385, 'duration': 5.045}, {'end': 1778.27, 'text': 'so what does f of f of ij state means?', 'start': 1773.43, 'duration': 4.84}, {'end': 1786.847, 'text': 'it says lcs of a string from zero to i and a string zero to j.', 'start': 1778.27, 'duration': 8.577}, {'end': 1787.828, 'text': "that's what it represents.", 'start': 1786.847, 'duration': 0.981}, {'end': 1793.211, 'text': 'right lcs of a string one zero to i and a zero to j.', 'start': 1787.828, 'duration': 5.383}, {'end': 1794.931, 'text': 'in this they want the length.', 'start': 1793.211, 'duration': 1.72}], 'summary': 'Analysis of string repetition and lcs representation for string lengths.', 'duration': 31.83, 'max_score': 1763.101, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/NPZn9jBrX8U/pics/NPZn9jBrX8U1763101.jpg'}, {'end': 1846.147, 'src': 'embed', 'start': 1824.432, 'weight': 4, 'content': [{'end': 1836.823, 'text': 'so you can easily just declare a dp of n cross m, initialize everything to as minus one and you can just go back and add these lines over here.', 'start': 1824.432, 'duration': 12.391}, {'end': 1838.705, 'text': 'this is a return statement, right.', 'start': 1836.823, 'duration': 1.882}, {'end': 1846.147, 'text': "so over here you can say okay, fine, i'll write dp of ij equal to this is a return statement.", 'start': 1839.881, 'duration': 6.266}], 'summary': 'Algorithm: use dynamic programming with n x m array initialized to -1.', 'duration': 21.715, 'max_score': 1824.432, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/NPZn9jBrX8U/pics/NPZn9jBrX8U1824432.jpg'}, {'end': 1942.605, 'src': 'embed', 'start': 1886.941, 'weight': 0, 'content': [{'end': 1894.226, 'text': 'make sure you pass the string by reference, because every time, if you create a new string, it might give you tle.', 'start': 1886.941, 'duration': 7.285}, {'end': 1894.886, 'text': 'this is what you wrote.', 'start': 1894.226, 'duration': 0.66}, {'end': 1897.528, 'text': 'this is what you wrote.', 'start': 1894.886, 'duration': 2.642}, {'end': 1899.109, 'text': 'return zero.', 'start': 1897.528, 'duration': 1.581}, {'end': 1910.009, 'text': "if they're matching, which is s of i equal to t of j, Then you're going to return 1, plus F of I minus 1, J minus 1, and an S and a T.", 'start': 1899.109, 'duration': 10.9}, {'end': 1913.111, 'text': "If they're not matching, you return the max of either both of them.", 'start': 1910.009, 'duration': 3.102}, {'end': 1916.533, 'text': 'Click And I minus 1, J, S, and T.', 'start': 1913.531, 'duration': 3.002}, {'end': 1919.454, 'text': 'Or you just go 1, which is S comma T.', 'start': 1916.533, 'duration': 2.921}, {'end': 1921.355, 'text': 'This is how the brute force will look.', 'start': 1919.454, 'duration': 1.901}, {'end': 1925.037, 'text': 'And obviously, you need to optimize this by applying Mimization.', 'start': 1921.516, 'duration': 3.521}, {'end': 1931.241, 'text': 'So just apply Mimization over here, which is DP of N cross vector of int.', 'start': 1925.558, 'duration': 5.683}, {'end': 1935.801, 'text': 'and m cross minus one.', 'start': 1933.599, 'duration': 2.202}, {'end': 1942.605, 'text': 'please make sure you pass the dp over here and once you pass the dp right over here, you can say vector of vector,', 'start': 1935.801, 'duration': 6.804}], 'summary': 'Pass string by reference to avoid tle. implement minimization for dp optimization.', 'duration': 55.664, 'max_score': 1886.941, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/NPZn9jBrX8U/pics/NPZn9jBrX8U1886941.jpg'}], 'start': 1737.369, 'title': 'State repetition in lcs algorithm and technique for applying memory action', 'summary': "Discusses the significance of state repetition in the lcs algorithm, noting examples of repeated states in larger sets of strings, and also explores the technique for applying memory action by optimizing the brute force approach with memoization and initializing a dp array of 'n cross m'.", 'chapters': [{'end': 1794.931, 'start': 1737.369, 'title': 'State repetition in lcs algorithm', 'summary': 'Discusses the repetition of states in the lcs algorithm, noting that larger examples demonstrate the repetition of states, such as f(0, -1) being repeated, indicating the significance of this phenomena in analyzing larger sets of strings.', 'duration': 57.562, 'highlights': ['The repetition of states, such as f(0, -1), becomes evident in larger examples, underscoring the significance of this phenomena in analyzing larger sets of strings.', 'The function f of f of ij state represents the longest common substring of a string from zero to i and a string from zero to j.']}, {'end': 1964.719, 'start': 1794.931, 'title': 'Technique for applying memory action', 'summary': "Discusses the technique to apply memory action by considering changing parameters 'i' and 'j', resulting in a requirement of 'n cross m' for dynamic programming, with a focus on optimizing the brute force approach by implementing memoization and initializing a dp array of 'n cross m'.", 'duration': 169.788, 'highlights': ["The technique to apply memory action involves considering changing parameters 'i' and 'j', resulting in a requirement of 'n cross m' for dynamic programming.", "Optimizing the brute force approach is achieved by implementing memoization and initializing a DP array of 'n cross m'.", "The function involves writing a function 'f' that takes 'int i' and 'int j' as parameters and passes the string by reference to avoid TLE.", "The brute force approach is optimized by applying memoization using a DP array of 'n cross m'."]}], 'duration': 227.35, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/NPZn9jBrX8U/pics/NPZn9jBrX8U1737369.jpg', 'highlights': ['The repetition of states, such as f(0, -1), becomes evident in larger examples, underscoring the significance of this phenomena in analyzing larger sets of strings.', "The technique to apply memory action involves considering changing parameters 'i' and 'j', resulting in a requirement of 'n cross m' for dynamic programming.", "Optimizing the brute force approach is achieved by implementing memoization and initializing a DP array of 'n cross m'.", 'The function f of f of ij state represents the longest common substring of a string from zero to i and a string from zero to j.', "The function involves writing a function 'f' that takes 'int i' and 'int j' as parameters and passes the string by reference to avoid TLE.", "The brute force approach is optimized by applying memoization using a DP array of 'n cross m'."]}, {'end': 2243.536, 'segs': [{'end': 2137.727, 'src': 'embed', 'start': 2050.762, 'weight': 0, 'content': [{'end': 2057.447, 'text': 'so you either eliminate a, which makes it cd, or you either eliminate d, which makes it a by c.', 'start': 2050.762, 'duration': 6.685}, {'end': 2063.833, 'text': 'over here, again in two directions, you either eliminate a or you either eliminate c.', 'start': 2057.447, 'duration': 6.386}, {'end': 2071.844, 'text': 'so if you carefully observe, one step two, step three, step four.', 'start': 2063.833, 'duration': 8.011}, {'end': 2077.771, 'text': 'so at max the depth is four, length two plus length two.', 'start': 2071.844, 'duration': 5.927}, {'end': 2084.743, 'text': 'because what we did was we deleted v, we deleted d, We deleted C.', 'start': 2077.771, 'duration': 6.972}, {'end': 2086.024, 'text': 'So, alternative deletions.', 'start': 2084.743, 'duration': 1.281}, {'end': 2090.324, 'text': 'If we do alternative deletions, there can be N deletions from string S1.', 'start': 2086.404, 'duration': 3.92}, {'end': 2092.665, 'text': 'There can be M deletions from string S2.', 'start': 2090.685, 'duration': 1.98}, {'end': 2096.786, 'text': 'Thereby, the auxiliary stack space will go as N plus M.', 'start': 2093.145, 'duration': 3.641}, {'end': 2100.467, 'text': "But obviously, as always, I'm not a big fan of N plus M.", 'start': 2096.786, 'duration': 3.681}, {'end': 2101.547, 'text': "So, I'll have to omit this.", 'start': 2100.467, 'duration': 1.08}, {'end': 2108.229, 'text': 'In order to omit this, I have to write the tabulation iterative bottom-up approach.', 'start': 2102.067, 'duration': 6.162}, {'end': 2110.369, 'text': 'Whatever you can call it.', 'start': 2109.489, 'duration': 0.88}, {'end': 2113.23, 'text': 'Okay So, bottom-up.', 'start': 2111.51, 'duration': 1.72}, {'end': 2115.042, 'text': "Rules I've already told you.", 'start': 2113.962, 'duration': 1.08}, {'end': 2117.903, 'text': 'What are the rules? Copy the base case.', 'start': 2115.302, 'duration': 2.601}, {'end': 2120.844, 'text': "I've already told you the rules.", 'start': 2119.683, 'duration': 1.161}, {'end': 2121.704, 'text': 'Copy the base case.', 'start': 2120.904, 'duration': 0.8}, {'end': 2126.185, 'text': 'Second, write down the changing parameters in the opposite fashion.', 'start': 2122.184, 'duration': 4.001}, {'end': 2129.745, 'text': 'Perfect Third, copy the recurrence.', 'start': 2126.585, 'duration': 3.16}, {'end': 2137.727, 'text': 'If you can follow these methods, I can guarantee that you can write any of the tabulations or bottom-up for any of the questions.', 'start': 2130.346, 'duration': 7.381}], 'summary': 'The depth is four, length two plus length two. n and m deletions from strings s1 and s2. tabulation iterative bottom-up approach guarantees writing any tabulations or bottom-up for any questions.', 'duration': 86.965, 'max_score': 2050.762, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/NPZn9jBrX8U/pics/NPZn9jBrX8U2050762.jpg'}, {'end': 2198.756, 'src': 'embed', 'start': 2167.701, 'weight': 1, 'content': [{'end': 2170.682, 'text': "If you remember the recursion tree, I'll just take you to the recursion tree that we did.", 'start': 2167.701, 'duration': 2.981}, {'end': 2177.006, 'text': 'In the recursion tree, the negative was minus 1, minus 1, minus 1.', 'start': 2171.543, 'duration': 5.463}, {'end': 2178.967, 'text': 'So we stopped at minus 1.', 'start': 2177.006, 'duration': 1.961}, {'end': 2183.49, 'text': "So we can't write cases for minus 1 in base cases.", 'start': 2178.967, 'duration': 4.523}, {'end': 2188.333, 'text': "Can you write for minus 1? Because how do you write dp of minus 1? That's not possible.", 'start': 2183.53, 'duration': 4.803}, {'end': 2190.752, 'text': "that's not possible.", 'start': 2189.531, 'duration': 1.221}, {'end': 2193.913, 'text': 'so what we do is we do a shifting of index.', 'start': 2190.752, 'duration': 3.161}, {'end': 2198.756, 'text': 'very simple, we do a shifting of index.', 'start': 2193.913, 'duration': 4.843}], 'summary': 'Recursion tree had 3 levels with -1, index shifting done', 'duration': 31.055, 'max_score': 2167.701, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/NPZn9jBrX8U/pics/NPZn9jBrX8U2167701.jpg'}], 'start': 1964.719, 'title': 'Debugging and tabulation techniques', 'summary': 'Covers debugging code issues and std c++, followed by the explanation of memoization with time and space complexity, and tabulation iterative bottom-up approach for string deletions with a maximum depth of four and auxiliary stack space of n plus m.', 'chapters': [{'end': 2050.762, 'start': 1964.719, 'title': 'Debugging code and optimizing time complexity', 'summary': 'Covers debugging code issues such as undeclared variables and use of std c++, followed by the explanation of memoization technique with time and space complexity of n cross m and tabulation technique with auxiliary stack space of n plus m.', 'duration': 86.043, 'highlights': ['Explaining memoization technique with time and space complexity of n cross m and n plus m in an auxiliary stack space', 'Debugging undeclared variables by using hash include with std c++', 'Emphasizing the need for tabulation technique to optimize auxiliary stack space and time complexity']}, {'end': 2243.536, 'start': 2050.762, 'title': 'Tabulation iterative approach for string deletions', 'summary': 'Explains the tabulation iterative bottom-up approach for string deletions, with a maximum depth of four and auxiliary stack space of n plus m. it emphasizes the shifting of index for writing tabulation and the base case handling for negative indexes.', 'duration': 192.774, 'highlights': ['The chapter emphasizes the tabulation iterative bottom-up approach for string deletions, with a maximum depth of four and auxiliary stack space of N plus M.', 'It highlights the importance of base case handling for negative indexes and the shifting of index for writing tabulation.']}], 'duration': 278.817, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/NPZn9jBrX8U/pics/NPZn9jBrX8U1964719.jpg', 'highlights': ['Explaining memoization technique with time and space complexity of n cross m and n plus m in an auxiliary stack space', 'Debugging undeclared variables by using hash include with std c++', 'Emphasizing the need for tabulation technique to optimize auxiliary stack space and time complexity', 'The chapter emphasizes the tabulation iterative bottom-up approach for string deletions, with a maximum depth of four and auxiliary stack space of N plus M.', 'It highlights the importance of base case handling for negative indexes and the shifting of index for writing tabulation.']}, {'end': 2819.567, 'segs': [{'end': 2401.931, 'src': 'embed', 'start': 2373.994, 'weight': 2, 'content': [{'end': 2377.256, 'text': 'and now, if i run this code, does this run same?', 'start': 2373.994, 'duration': 3.262}, {'end': 2378.357, 'text': 'it will?', 'start': 2377.256, 'duration': 1.101}, {'end': 2379.497, 'text': 'why will it?', 'start': 2378.357, 'duration': 1.14}, {'end': 2380.898, 'text': "because you've just shifted it.", 'start': 2379.497, 'duration': 1.401}, {'end': 2382.239, 'text': "okay, it's giving runtime error.", 'start': 2380.898, 'duration': 1.341}, {'end': 2383.68, 'text': 'why does it give runtime error?', 'start': 2382.239, 'duration': 1.441}, {'end': 2387.522, 'text': "because the dp that you've declared is of n m and you are now using the states of nm.", 'start': 2383.68, 'duration': 3.842}, {'end': 2391.965, 'text': 'So just make sure you declare a DP of extra size, m plus 1..', 'start': 2387.902, 'duration': 4.063}, {'end': 2397.728, 'text': "And now, you've done a shifting of index one right and it does work fine.", 'start': 2391.965, 'duration': 5.763}, {'end': 2398.849, 'text': 'So, okay.', 'start': 2398.309, 'duration': 0.54}, {'end': 2401.931, 'text': 'So, the base case has been, now the base case has changed.', 'start': 2399.189, 'duration': 2.742}], 'summary': 'Code gives runtime error due to shifting index without updating dp size.', 'duration': 27.937, 'max_score': 2373.994, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/NPZn9jBrX8U/pics/NPZn9jBrX8U2373994.jpg'}, {'end': 2450.886, 'src': 'embed', 'start': 2426.723, 'weight': 4, 'content': [{'end': 2434.286, 'text': 'And what does this mean? i can be anything, but this guy has to be 0.', 'start': 2426.723, 'duration': 7.563}, {'end': 2438.668, 'text': 'And what can be the possible values of j? Anything from 0 to m minus 1.', 'start': 2434.286, 'duration': 4.382}, {'end': 2441.169, 'text': 'What can be the possible values of i? Anything from 0 to n minus 1.', 'start': 2438.668, 'duration': 2.501}, {'end': 2442.049, 'text': "I'll loop it.", 'start': 2441.169, 'duration': 0.88}, {'end': 2444.984, 'text': 'base case are very simple.', 'start': 2443.004, 'duration': 1.98}, {'end': 2450.886, 'text': 'j can be anything from 0 to m, minus 1 and dp of 0, and j will be 0.', 'start': 2444.984, 'duration': 5.902}], 'summary': 'I can be anything, j from 0 to m-1, i from 0 to n-1', 'duration': 24.163, 'max_score': 2426.723, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/NPZn9jBrX8U/pics/NPZn9jBrX8U2426723.jpg'}, {'end': 2653.083, 'src': 'embed', 'start': 2596.425, 'weight': 1, 'content': [{'end': 2605.147, 'text': 'and what you can do is you can also remove this portion and instead of f, just make sure you write dp of i minus 1 j.', 'start': 2596.425, 'duration': 8.722}, {'end': 2617.85, 'text': 'perfect. and over here you can write max of dp of i minus 1 j and again you can just remove this portion.', 'start': 2605.147, 'duration': 12.703}, {'end': 2623.387, 'text': 'There is a comma of dp of i and j minus 1..', 'start': 2619.585, 'duration': 3.802}, {'end': 2624.708, 'text': 'And again, please make sure you remove this.', 'start': 2623.387, 'duration': 1.321}, {'end': 2627.41, 'text': "Yeah, that's what it will be.", 'start': 2625.889, 'duration': 1.521}, {'end': 2629.972, 'text': 'So if I now try to run this, probably should run.', 'start': 2627.79, 'duration': 2.182}, {'end': 2636.316, 'text': "If I've not done syntax mistakes, again, the hashing load missing.", 'start': 2631.292, 'duration': 5.024}, {'end': 2638.677, 'text': "Again, it's giving us a wrong answer.", 'start': 2637.536, 'duration': 1.141}, {'end': 2643.04, 'text': "Why is that? So we will check out why is this giving us a wrong answer, and then we'll get started.", 'start': 2638.897, 'duration': 4.143}, {'end': 2650.842, 'text': 'So why did this give us a wrong answer? Because in the recursion, if this if executed, it went back from there.', 'start': 2644.42, 'duration': 6.422}, {'end': 2653.083, 'text': 'Over here, you have to just make sure you write an else.', 'start': 2651.423, 'duration': 1.66}], 'summary': 'Discussing code optimization and debugging errors in the algorithm.', 'duration': 56.658, 'max_score': 2596.425, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/NPZn9jBrX8U/pics/NPZn9jBrX8U2596425.jpg'}, {'end': 2789.918, 'src': 'embed', 'start': 2762.242, 'weight': 0, 'content': [{'end': 2766.206, 'text': 'Okay, so the issue was previous equal to curr will be here, not curr equal to previous, my bad.', 'start': 2762.242, 'duration': 3.964}, {'end': 2769.749, 'text': 'Okay, so if I just give it a submit, I should be running fine now.', 'start': 2766.866, 'duration': 2.883}, {'end': 2771.819, 'text': 'That should run.', 'start': 2771.198, 'duration': 0.621}, {'end': 2775.022, 'text': 'If I give it a submit, this will definitely run.', 'start': 2771.839, 'duration': 3.183}, {'end': 2778.886, 'text': 'So guys, I hope you have understood how I took a memoization solution.', 'start': 2775.583, 'duration': 3.303}, {'end': 2787.075, 'text': 'And since we were having problem in tabulation, I shifted it by right so that we do not have negative integers or negative indexes in these cases.', 'start': 2779.367, 'duration': 7.708}, {'end': 2789.918, 'text': 'And after that, I just simply converted that into a tabulated.', 'start': 2787.455, 'duration': 2.463}], 'summary': 'Corrected code for memoization solution, avoiding negative integers and converted to tabulated.', 'duration': 27.676, 'max_score': 2762.242, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/NPZn9jBrX8U/pics/NPZn9jBrX8U2762242.jpg'}], 'start': 2243.536, 'title': 'Dp index shifting and tabulation', 'summary': 'Covers shifting the index for dynamic programming, altering base cases, implementing tabulation format of lcs, resulting in runtime errors, and the need for space optimization. it also discusses memoization solution, shift to tabulation, handling negative integers and indexes, focusing on space optimization, and recommends viewing previous dp lectures.', 'chapters': [{'end': 2700.156, 'start': 2243.536, 'title': 'Shifting index for dp', 'summary': 'Discusses shifting the index for dynamic programming, altering the base case, and implementing the tabulation format of lcs, resulting in runtime errors, and the need for space optimization.', 'duration': 456.62, 'highlights': ['Shifting the index for dynamic programming', 'Altering the base case and tabulation format', 'Runtime error due to using states of nm with a dp of nm', 'Space optimization for dynamic programming']}, {'end': 2819.567, 'start': 2700.637, 'title': 'Memoization and tabulation in dp', 'summary': 'Discusses the implementation of a memoization solution and the shift to tabulation, addressing issues with negative integers and negative indexes, with a focus on space optimization and a recommendation to view previous dp lectures for a better understanding.', 'duration': 118.93, 'highlights': ['The space optimization in tabulated is an extension of previous DP lectures, emphasizing the importance of space optimization in dynamic programming.', 'The shift from memoization to tabulation was made to avoid negative integers or negative indexes, leading to a successful conversion into a tabulated solution.', 'Recommendation to view previous DP lectures for understanding space optimization, highlighting its significance in dynamic programming.']}], 'duration': 576.031, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/NPZn9jBrX8U/pics/NPZn9jBrX8U2243536.jpg', 'highlights': ['Space optimization for dynamic programming', 'The shift from memoization to tabulation for avoiding negative integers or indexes', 'Shifting the index for dynamic programming', 'Altering the base case and tabulation format', 'Runtime error due to using states of nm with a dp of nm', 'The space optimization in tabulated is an extension of previous DP lectures', 'Recommendation to view previous DP lectures for understanding space optimization']}], 'highlights': ['Mastering DP on strings guarantees solving related problems', 'DP on strings involves comparison, replacements, and edits', 'Number of subsequences for a string of length n is 2^n', 'Recursion with parameters generates subsequences', 'Dynamic programming considers different scenarios and indexes', 'Optimizing algorithm through memoization improves efficiency', 'Repetition of states becomes evident in larger examples', "Memory action involves changing parameters 'i' and 'j'", 'Optimizing brute force approach by implementing memoization', 'Memoization technique has time and space complexity of n x m', 'Emphasizing the need for tabulation technique to optimize space', 'Space optimization for dynamic programming', 'Shift from memoization to tabulation for avoiding negative indexes', 'Runtime error due to using states of nm with a dp of nm']}