title

DP 26. Print Longest Common Subsequence | 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 print the LCS. Please watch DP 25 before watching this.
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 26. Print Longest Common Subsequence | Dp on Strings', 'heatmap': [{'end': 815.945, 'start': 797.029, 'weight': 0.739}, {'end': 903.901, 'start': 848.736, 'weight': 0.709}, {'end': 944.443, 'start': 911.703, 'weight': 0.775}, {'end': 990.425, 'start': 971.69, 'weight': 0.736}], 'summary': "Covers techniques for solving the longest common subsequence problem, demonstrating memoization, tabulation, and space optimization, with the longest common subsequence having a length of 3 and the string 'bde' as the lcs. it also explains dynamic programming summation, tabulation, string indexing, and length, and illustrates dynamic programming formulas, showing a maximum value of 3 for dp of 5 and 5. additionally, it analyzes the lcs algorithm, emphasizing its simplicity and discussing its time complexity of n cross m and worst-case backtracking time complexity of n plus m.", 'chapters': [{'end': 67.17, 'segs': [{'end': 67.17, 'src': 'embed', 'start': 0.269, 'weight': 0, 'content': [{'end': 2.331, 'text': 'Hey, everyone, welcome back to take you forward.', 'start': 0.269, 'duration': 2.062}, {'end': 6.594, 'text': 'so in the previous video we did solve the LCS.', 'start': 2.331, 'duration': 4.263}, {'end': 11.637, 'text': 'we did learn about the memoization technique, the tabulation technique and the space optimization technique.', 'start': 6.594, 'duration': 5.043}, {'end': 14.559, 'text': 'but what did we learn about, learn over there?', 'start': 11.637, 'duration': 2.922}, {'end': 16.061, 'text': 'we will be given couple of strings.', 'start': 14.559, 'duration': 1.502}, {'end': 24.725, 'text': 'we did learn how to print the length of the longest common subsequence, like the length over here is 3.', 'start': 16.921, 'duration': 7.804}, {'end': 30.687, 'text': 'so we did learn how to print the length of the longest common subsequence and we got it as 3.', 'start': 24.725, 'duration': 5.962}, {'end': 33.328, 'text': 'now, what if I change the question?', 'start': 30.687, 'duration': 2.641}, {'end': 36.81, 'text': "the question might ask you okay, it's fine, you're giving me the length.", 'start': 33.328, 'duration': 3.482}, {'end': 39.792, 'text': 'what if I want the string?', 'start': 37.31, 'duration': 2.482}, {'end': 41.713, 'text': 'yes, what if I want the string?', 'start': 39.792, 'duration': 1.921}, {'end': 42.454, 'text': 'like over here?', 'start': 41.713, 'duration': 0.741}, {'end': 45.036, 'text': 'the longest common subsequence is nothing.', 'start': 42.454, 'duration': 2.582}, {'end': 51.24, 'text': "but if I carefully see, I will have a B, I will have a B, I will have a D, I'll have a D, I'll have a E.", 'start': 45.036, 'duration': 6.204}, {'end': 54.503, 'text': 'so I can say the string is BDE.', 'start': 51.24, 'duration': 3.263}, {'end': 56.884, 'text': 'this is the LCS.', 'start': 54.503, 'duration': 2.381}, {'end': 60.707, 'text': 'what if someone comes up and says hey, can you please print me the LCS?', 'start': 56.884, 'duration': 3.823}, {'end': 61.328, 'text': 'can you do this?', 'start': 60.707, 'duration': 0.621}, {'end': 65.449, 'text': 'You can do it via brute force, but can you do it in an optimized way?', 'start': 62.068, 'duration': 3.381}, {'end': 67.17, 'text': 'I think we can.', 'start': 66.49, 'duration': 0.68}], 'summary': "Learned about solving lcs with memoization and tabulation techniques, obtaining a length of 3 and the string 'bde'.", 'duration': 66.901, 'max_score': 0.269, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/-zI4mrF2Pb4/pics/-zI4mrF2Pb4269.jpg'}], 'start': 0.269, 'title': 'Longest common subsequence', 'summary': "Covers techniques such as memoization, tabulation, and space optimization for solving the longest common subsequence problem, and demonstrates how to find the length and the actual string of the longest common subsequence, with the length being 3 and the string 'bde' as the lcs.", 'chapters': [{'end': 67.17, 'start': 0.269, 'title': 'Longest common subsequence', 'summary': "Covers techniques such as memoization, tabulation, and space optimization for solving the longest common subsequence problem, and demonstrates how to find the length and the actual string of the longest common subsequence, with the length being 3 and the string 'bde' as the lcs.", 'duration': 66.901, 'highlights': ['The chapter demonstrates solving the Longest Common Subsequence problem using memoization, tabulation, and space optimization techniques.', 'It covers finding the length of the longest common subsequence, which is 3 in the given example.', "It also shows how to find the actual string of the longest common subsequence, which is 'BDE' in the given example."]}], 'duration': 66.901, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/-zI4mrF2Pb4/pics/-zI4mrF2Pb4269.jpg', 'highlights': ['Covers techniques such as memoization, tabulation, and space optimization for solving the longest common subsequence problem.', 'Demonstrates finding the length of the longest common subsequence, which is 3 in the given example.', "Shows how to find the actual string of the longest common subsequence, which is 'BDE' in the given example."]}, {'end': 297.961, 'segs': [{'end': 125.22, 'src': 'embed', 'start': 93.999, 'weight': 0, 'content': [{'end': 97.139, 'text': "let's simply, uh, print the dp array.", 'start': 93.999, 'duration': 3.14}, {'end': 103.161, 'text': "okay, that's, uh, zero j less than equal to m and j plus plus.", 'start': 97.139, 'duration': 6.022}, {'end': 105.682, 'text': 'i can be like c out of dp of i, j.', 'start': 103.161, 'duration': 2.521}, {'end': 110.103, 'text': 'Okay, and this is something we can go and see how to handle.', 'start': 106.98, 'duration': 3.123}, {'end': 115.95, 'text': "Perfect So let's quickly print the dp array and let's see what is the dp array coming across.", 'start': 110.464, 'duration': 5.486}, {'end': 120.695, 'text': 'So this is what the dp array looks like and this is the answer 3.', 'start': 116.751, 'duration': 3.944}, {'end': 125.22, 'text': "So let's write this in our iPad and then I'll be explaining you.", 'start': 120.695, 'duration': 4.525}], 'summary': 'Printing the dp array, resulting in an answer of 3.', 'duration': 31.221, 'max_score': 93.999, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/-zI4mrF2Pb4/pics/-zI4mrF2Pb493999.jpg'}, {'end': 174.295, 'src': 'embed', 'start': 142.446, 'weight': 2, 'content': [{'end': 145.449, 'text': "that's why, if i write down the indexes, this is the zeroth index.", 'start': 142.446, 'duration': 3.003}, {'end': 145.99, 'text': 'first index.', 'start': 145.449, 'duration': 0.541}, {'end': 146.49, 'text': 'second index.', 'start': 145.99, 'duration': 0.5}, {'end': 146.971, 'text': 'third index.', 'start': 146.49, 'duration': 0.481}, {'end': 147.431, 'text': 'fourth index.', 'start': 146.971, 'duration': 0.46}, {'end': 148.352, 'text': 'fifth index.', 'start': 147.431, 'duration': 0.921}, {'end': 148.913, 'text': 'this is zero.', 'start': 148.352, 'duration': 0.561}, {'end': 149.413, 'text': 'this is the first.', 'start': 148.913, 'duration': 0.5}, {'end': 150.955, 'text': 'this is the second, this is the third, this is the fourth.', 'start': 149.413, 'duration': 1.542}, {'end': 152.136, 'text': 'this is the fifth.', 'start': 150.955, 'duration': 1.181}, {'end': 164.17, 'text': 'and if we take the string s1 equal to a, b, c, d, e and s2 equal to b, d, g, e, k, so this is a string of length 5.', 'start': 152.136, 'duration': 12.034}, {'end': 169.212, 'text': 'but if I write down the index is 0, 1, 2, 3, 4, but the answer is stored over here, like.', 'start': 164.17, 'duration': 5.042}, {'end': 174.295, 'text': 'if you carefully see, the answer is stored over here in a, 5 and a, 5.', 'start': 169.212, 'duration': 5.083}], 'summary': 'Explanation of indexes and string lengths with examples.', 'duration': 31.849, 'max_score': 142.446, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/-zI4mrF2Pb4/pics/-zI4mrF2Pb4142446.jpg'}, {'end': 290.917, 'src': 'embed', 'start': 262.016, 'weight': 1, 'content': [{'end': 265.219, 'text': 'so in this, what is the length of the lcs?', 'start': 262.016, 'duration': 3.203}, {'end': 265.84, 'text': "that's two.", 'start': 265.219, 'duration': 0.621}, {'end': 269.523, 'text': 'if you carefully observe, we have a b, we have a d and we have bd.', 'start': 265.84, 'duration': 3.683}, {'end': 272.386, 'text': 'the length of the longest common subsequence is two.', 'start': 269.523, 'duration': 2.863}, {'end': 274.487, 'text': 'thereby the dp array stores the two over here.', 'start': 272.386, 'duration': 2.101}, {'end': 278.05, 'text': 'similarly, if i say why is the one stored over here?', 'start': 275.308, 'duration': 2.742}, {'end': 280.551, 'text': 'because in this bd, why is the one stored over here?', 'start': 278.05, 'duration': 2.501}, {'end': 286.794, 'text': "because in this bdge and in this abc there is only one thing common, that's b.", 'start': 280.551, 'duration': 6.243}, {'end': 288.215, 'text': 'thereby one is stored over here.', 'start': 286.794, 'duration': 1.421}, {'end': 290.917, 'text': "that's the meaning of dps.", 'start': 288.215, 'duration': 2.702}], 'summary': "The length of the longest common subsequence (lcs) is two, with 'bd' common in 'bdge' and 'abc'.", 'duration': 28.901, 'max_score': 262.016, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/-zI4mrF2Pb4/pics/-zI4mrF2Pb4262016.jpg'}], 'start': 67.71, 'title': 'Dynamic programming and string indexing', 'summary': 'Covers dynamic programming summation and tabulation, demonstrating the creation and printing of a dp array with a final result of 3. it also explains string indexing and length, using examples to illustrate zero-based and one-based indexing.', 'chapters': [{'end': 141.966, 'start': 67.71, 'title': 'Dynamic programming summation and tabulation', 'summary': 'Discusses the process of dynamic programming summation and tabulation, including the demonstration of creating and printing a dp array, with a final result of 3.', 'duration': 74.256, 'highlights': ['The chapter explains the process of dynamic programming summation and tabulation, including the demonstration of creating and printing a DP array, which resulted in an answer of 3.', 'The speaker goes through the detailed steps of creating and printing a DP array, emphasizing the conversion into one-based indexing and row and column numbers.']}, {'end': 192.43, 'start': 142.446, 'title': 'String indexing and length', 'summary': 'Discusses string indexing and length, demonstrating how to index a string and calculate its length, using a specific example of two strings and highlighting the use of zero-based indexing and one-based indexing.', 'duration': 49.984, 'highlights': ['The string s1 has a length of 5, represented by the characters a, b, c, d, e.', 'The answer is stored using zero-based indexing, with the result being a, 5 and a, 5.', 'The indexing is demonstrated by showing the zeroth index, first index, second index, third index, fourth index, and fifth index.']}, {'end': 297.961, 'start': 192.43, 'title': 'Understanding dynamic programming', 'summary': 'Explains the concept of dynamic programming and how it stores information to compute the answer, using examples and explanations to demonstrate the process and significance of the stored values.', 'duration': 105.531, 'highlights': ["The longest common subsequence (LCS) length of 'BD' in the strings 'ABCD' and 'abcd' is 2, thereby the DP array stores the value 2 at index (4, 2).", "The DP array stores the value 1 at index (2, 4) because 'bdge' and 'abc' have only 'b' in common, representing the meaning of DPS.", 'The significance of the stored values in the DP array is explained through examples, such as storing the value 3 at index (5, 5) and the value 1 at index (4, 2).']}], 'duration': 230.251, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/-zI4mrF2Pb4/pics/-zI4mrF2Pb467710.jpg', 'highlights': ['The chapter explains the process of dynamic programming summation and tabulation, including the demonstration of creating and printing a DP array, which resulted in an answer of 3.', "The longest common subsequence (LCS) length of 'BD' in the strings 'ABCD' and 'abcd' is 2, thereby the DP array stores the value 2 at index (4, 2).", 'The string s1 has a length of 5, represented by the characters a, b, c, d, e.']}, {'end': 487.649, 'segs': [{'end': 382, 'src': 'embed', 'start': 298.681, 'weight': 0, 'content': [{'end': 309.965, 'text': 'so if i ask you what are the formulas that you wrote, you wrote a simple formula dp of i, j is equal to 1, plus dp of i minus 1 and j minus 1.', 'start': 298.681, 'duration': 11.284}, {'end': 320.008, 'text': 'and this did happen when, when these guys were equal like s of i, minus 1 was equal to equal to like s of 2 j minus 1..', 'start': 309.965, 'duration': 10.043}, {'end': 321.148, 'text': 'this is when you wrote this.', 'start': 320.008, 'duration': 1.14}, {'end': 323.269, 'text': 'remember, this is the first condition that you wrote.', 'start': 321.148, 'duration': 2.121}, {'end': 326.146, 'text': 'else what did you write?', 'start': 324.464, 'duration': 1.682}, {'end': 336.734, 'text': 'or else you wrote very simple condition dp of i j was max of dp of i minus 1 j.', 'start': 326.146, 'duration': 10.588}, {'end': 343.48, 'text': 'that means previous row, same column, and dp of i comma j, minus 1, same row, previous uh column.', 'start': 336.734, 'duration': 6.746}, {'end': 346.783, 'text': 'this is what you wrote, either the upper one or the down.', 'start': 343.48, 'duration': 3.303}, {'end': 350.506, 'text': 'either this one or either this one is what you wrote.', 'start': 346.783, 'duration': 3.723}, {'end': 355.807, 'text': 'so if i ask you a very, very straightforward question Over here, we have a 3, right?', 'start': 350.506, 'duration': 5.301}, {'end': 360.152, 'text': 'And we have a E and we have a K.', 'start': 356.548, 'duration': 3.604}, {'end': 363.214, 'text': 'Do they match? I say no.', 'start': 360.152, 'duration': 3.062}, {'end': 371.482, 'text': "So basically when the tabulation will go across, like I'll show you in the code, basically what happens is there's an I and there's a J.", 'start': 364.055, 'duration': 7.427}, {'end': 372.243, 'text': 'So they will be running.', 'start': 371.482, 'duration': 0.761}, {'end': 382, 'text': 'So whenever they will be at this stage, from where does this 3 come? Whenever you are at this portion and you are trying to fill up DP of 5 and 5.', 'start': 372.703, 'duration': 9.297}], 'summary': 'Discussion on writing formulas for dynamic programming with examples and conditions, including matching characters and tabulation.', 'duration': 83.319, 'max_score': 298.681, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/-zI4mrF2Pb4/pics/-zI4mrF2Pb4298681.jpg'}, {'end': 463.389, 'src': 'embed', 'start': 406.756, 'weight': 3, 'content': [{'end': 415.281, 'text': 'uh, sorry, this is i minus one comma j and this is i comma j, minus one either of these guys maximum comes and gets stored over here.', 'start': 406.756, 'duration': 8.525}, {'end': 416.261, 'text': 'thereby this.', 'start': 415.281, 'duration': 0.98}, {'end': 418.223, 'text': 'three did come from here three.', 'start': 416.261, 'duration': 1.962}, {'end': 422.174, 'text': "so what you'll do is you'll say okay, fine, We came from here.", 'start': 418.223, 'duration': 3.951}, {'end': 423.355, 'text': 'So you will go over here.', 'start': 422.214, 'duration': 1.141}, {'end': 425.616, 'text': 'You will straight forward go over there.', 'start': 423.875, 'duration': 1.741}, {'end': 428.477, 'text': 'Right You start from this last guy.', 'start': 426.096, 'duration': 2.381}, {'end': 430.798, 'text': 'Which is N cross M.', 'start': 428.797, 'duration': 2.001}, {'end': 432.438, 'text': 'And then you start moving.', 'start': 430.798, 'duration': 1.64}, {'end': 433.859, 'text': 'Start moving the pointer.', 'start': 432.738, 'duration': 1.121}, {'end': 435.399, 'text': 'So right over here.', 'start': 434.179, 'duration': 1.22}, {'end': 436.42, 'text': 'You are here.', 'start': 436.039, 'duration': 0.381}, {'end': 439.181, 'text': 'Now This is an E.', 'start': 436.86, 'duration': 2.321}, {'end': 440.301, 'text': 'This is an E.', 'start': 439.181, 'duration': 1.12}, {'end': 442.422, 'text': 'Which means they are a match.', 'start': 440.301, 'duration': 2.121}, {'end': 444.102, 'text': 'They are a match.', 'start': 443.022, 'duration': 1.08}, {'end': 445.423, 'text': 'And if they are a match.', 'start': 444.543, 'duration': 0.88}, {'end': 450.425, 'text': 'Where will this 3 come in from? Where will this 3 come in from? This 3 will come from.', 'start': 445.783, 'duration': 4.642}, {'end': 457.967, 'text': '1 plus something on i minus 1 and j minus 1.', 'start': 452.385, 'duration': 5.582}, {'end': 459.928, 'text': 'what is i minus 1 and j minus 1?', 'start': 457.967, 'duration': 1.961}, {'end': 463.389, 'text': "that's nothing but this guy.", 'start': 459.928, 'duration': 3.461}], 'summary': 'Algorithm explanation with step-by-step movement and matching criteria.', 'duration': 56.633, 'max_score': 406.756, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/-zI4mrF2Pb4/pics/-zI4mrF2Pb4406756.jpg'}], 'start': 298.681, 'title': 'Dynamic programming concepts', 'summary': 'Covers dynamic programming formulas and explanations with examples, demonstrating the process of finding maximum values and matches based on specific conditions and variables, including a maximum value of 3 for dp of 5 and 5.', 'chapters': [{'end': 355.807, 'start': 298.681, 'title': 'Dynamic programming formulas', 'summary': 'Discusses the dynamic programming formulas for finding the value of dp of i, j with conditions based on the comparison of s of i, j and s of i-1, j-1, as well as the selection of max values from the previous row and previous column.', 'duration': 57.126, 'highlights': ['The formula dp of i, j is equal to 1 + dp of i - 1 and j - 1, used when s of i - 1 is equal to s of 2j - 1.', 'The condition for dp of i, j is the maximum of dp of i - 1, j and dp of i, j - 1, selecting either the value from the previous row or the previous column.']}, {'end': 406.756, 'start': 356.548, 'title': 'Dynamic programming explanation', 'summary': 'Explains the concept of dynamic programming using variables e, k, i, j, and the process of filling up dp of 5 and 5 with a maximum value of 3.', 'duration': 50.208, 'highlights': ['The process involves comparing variables E and K to determine if they match, and filling up DP of 5 and 5 with a maximum value of 3.', 'Explanation of the running of variables I and J during the tabulation process.', 'Clarification on how the value of 3 is obtained in the context of matching variables E and K.']}, {'end': 487.649, 'start': 406.756, 'title': 'Dynamic programming explanation', 'summary': 'Explains a dynamic programming concept with an example of matching elements, demonstrating the process of storing and retrieving values and using them to find the maximum and matches.', 'duration': 80.893, 'highlights': ['The maximum value is stored by comparing i minus one comma j and i comma j, thereby determining the path for finding the maximum. (Relevance: 5)', "The process of retrieving and storing values is demonstrated using the example of matching 'E' elements, with the explanation of how the value is retrieved and written in the new position. (Relevance: 4)", 'The concept of matching elements and the process of finding the maximum and storing the matches is explained using a step-by-step example, emphasizing the iterative movement and value comparisons. (Relevance: 3)']}], 'duration': 188.968, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/-zI4mrF2Pb4/pics/-zI4mrF2Pb4298681.jpg', 'highlights': ['The formula dp of i, j is equal to 1 + dp of i - 1 and j - 1, used when s of i - 1 is equal to s of 2j - 1.', 'The condition for dp of i, j is the maximum of dp of i - 1, j and dp of i, j - 1, selecting either the value from the previous row or the previous column.', 'The process involves comparing variables E and K to determine if they match, and filling up DP of 5 and 5 with a maximum value of 3.', 'The maximum value is stored by comparing i minus one comma j and i comma j, thereby determining the path for finding the maximum. (Relevance: 5)', "The process of retrieving and storing values is demonstrated using the example of matching 'E' elements, with the explanation of how the value is retrieved and written in the new position. (Relevance: 4)", 'The concept of matching elements and the process of finding the maximum and storing the matches is explained using a step-by-step example, emphasizing the iterative movement and value comparisons. (Relevance: 3)']}, {'end': 1005.349, 'segs': [{'end': 821.332, 'src': 'heatmap', 'start': 797.029, 'weight': 0.739, 'content': [{'end': 804.055, 'text': 'so I will, like I please move towards I minus 1 or J, move towards J minus 1, like in this case.', 'start': 797.029, 'duration': 7.026}, {'end': 805.856, 'text': 'J will happen in the.', 'start': 804.055, 'duration': 1.801}, {'end': 808.739, 'text': 'in our case, J would have moved right.', 'start': 805.856, 'duration': 2.883}, {'end': 815.945, 'text': 'so in this way you can move the I pointers and the J pointers correct in the next I pointers or J pointers in the next step.', 'start': 808.739, 'duration': 7.206}, {'end': 818.43, 'text': 'you are over here.', 'start': 816.789, 'duration': 1.641}, {'end': 821.332, 'text': 'you saw this guy matching with this guy.', 'start': 818.43, 'duration': 2.902}], 'summary': 'Moving pointers in the algorithm to match characters.', 'duration': 24.303, 'max_score': 797.029, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/-zI4mrF2Pb4/pics/-zI4mrF2Pb4797029.jpg'}, {'end': 903.901, 'src': 'heatmap', 'start': 848.736, 'weight': 0.709, 'content': [{'end': 853.118, 'text': 'and then you know the answer is i equal to zero till length.', 'start': 848.736, 'duration': 4.382}, {'end': 854.139, 'text': 'so s plus equal to.', 'start': 853.118, 'duration': 1.021}, {'end': 864.884, 'text': 'probably you can, uh, just assign some uh, dummy dollar values, assign a dummy dummy array, dummy string of dollar, dollar, dollar assigned.', 'start': 854.139, 'duration': 10.745}, {'end': 871.867, 'text': 'okay, and probably what you can do is you can keep an index equal to length, minus one, right.', 'start': 864.884, 'duration': 6.983}, {'end': 878.589, 'text': 'and if this is the case, then you can say okay, in our string or in our lcs string,', 'start': 871.867, 'duration': 6.722}, {'end': 888.812, 'text': "in index i will store s1 of i minus 1 and the next moment i'll shift the index so that why am i doing this?", 'start': 878.589, 'duration': 10.223}, {'end': 896.994, 'text': "so that remember, whenever this e, whenever this e and this e match, i'll store e where there was the index,", 'start': 888.812, 'duration': 8.182}, {'end': 900.98, 'text': "then i'll move the index to the previous so that for the next step it gets stored Perfect.", 'start': 896.994, 'duration': 3.986}, {'end': 903.901, 'text': 'We have stored the index and we have moved the index back.', 'start': 901.4, 'duration': 2.501}], 'summary': 'The transcript discusses index manipulation and string assignment in a programming context.', 'duration': 55.165, 'max_score': 848.736, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/-zI4mrF2Pb4/pics/-zI4mrF2Pb4848736.jpg'}, {'end': 990.425, 'src': 'heatmap', 'start': 911.703, 'weight': 0, 'content': [{'end': 916.685, 'text': 'Why? Because they have to move to the diagonal.', 'start': 911.703, 'duration': 4.982}, {'end': 920.406, 'text': 'So thereby, it will move to i-1 and j-1.', 'start': 917.205, 'duration': 3.201}, {'end': 923.407, 'text': 'So this is the entire set of code.', 'start': 920.966, 'duration': 2.441}, {'end': 926.488, 'text': 'If you write, you will be able to print the answer.', 'start': 923.487, 'duration': 3.001}, {'end': 935.155, 'text': "So if you see in the code as well, I've written the exact same thing, taken the length, signed the answer and then indexed, exact the same thing.", 'start': 927.208, 'duration': 7.947}, {'end': 941.681, 'text': 'And if I take both the strings and if I just run it, you will see that the string is getting printed.', 'start': 935.595, 'duration': 6.086}, {'end': 944.443, 'text': "So that's how you can print the LCS.", 'start': 941.741, 'duration': 2.702}, {'end': 948.927, 'text': 'So the time complexity will be definitely n cross m.', 'start': 945.024, 'duration': 3.903}, {'end': 953.752, 'text': 'You have to use the tabulated, like you have to use the entire 2D array so that you can backtrack.', 'start': 948.927, 'duration': 4.825}, {'end': 956.156, 'text': 'and you can simply backtrack.', 'start': 954.553, 'duration': 1.603}, {'end': 960.024, 'text': 'and what will be the time complexity to backtrack?', 'start': 956.156, 'duration': 3.868}, {'end': 961.808, 'text': 'ask about the time complexity.', 'start': 960.024, 'duration': 1.784}, {'end': 971.69, 'text': 'the worst case can be n plus m, assuming, uh, in the matrix, uh, you are backtracking something like this.', 'start': 961.808, 'duration': 9.882}, {'end': 974.812, 'text': 'and then you move straight like you started from the right corner.', 'start': 971.69, 'duration': 3.122}, {'end': 978.655, 'text': 'you move like this, then you move like this, so you take all the columns and all the rows.', 'start': 974.812, 'duration': 3.843}, {'end': 984.22, 'text': 'so n plus m at the worst case is what you will backtrack.', 'start': 978.655, 'duration': 5.565}, {'end': 987.122, 'text': "that's, that's a simple, uh, lcs stuff.", 'start': 984.22, 'duration': 2.902}, {'end': 990.425, 'text': "and before that, n into m plus n plus m is what you'll be requiring.", 'start': 987.122, 'duration': 3.303}], 'summary': 'Print the lcs with time complexity of n*m and backtrack of n+m.', 'duration': 63.109, 'max_score': 911.703, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/-zI4mrF2Pb4/pics/-zI4mrF2Pb4911703.jpg'}], 'start': 487.649, 'title': 'Lcs algorithm analysis', 'summary': 'Illustrates the process of finding the longest common subsequence (lcs) of two strings using dynamic programming, emphasizing the simplicity of the code and discussing the time complexity of the algorithm, with a time complexity of n cross m and a worst-case backtracking time complexity of n plus m.', 'chapters': [{'end': 1005.349, 'start': 487.649, 'title': 'Lcs algorithm analysis', 'summary': 'Illustrates the process of finding the longest common subsequence (lcs) of two strings using dynamic programming, emphasizing the simplicity of the code and discussing the time complexity of the algorithm, with a time complexity of n cross m and a worst-case backtracking time complexity of n plus m.', 'duration': 517.7, 'highlights': ['The time complexity of the algorithm is n cross m, and the worst-case backtracking time complexity is n plus m, making it an efficient solution for finding the longest common subsequence (LCS) of two strings.', 'The process involves checking for matches between characters in the two strings, determining the maximum length of the common subsequence, and efficiently backtracking to find the LCS, ensuring simplicity and straightforwardness in the code implementation.', 'The algorithm involves using a 2D array for tabulation, and the time complexity for backtracking is n plus m in the worst case, providing a comprehensive understanding of the process and the associated complexities.', 'The presenter emphasizes the importance of understanding and implementing the algorithm, providing a clear explanation of the process and its time complexities, and encourages engagement with the content through likes and subscriptions.', 'The chapter concludes by summarizing the key points of finding the longest common subsequence and encourages viewer engagement through likes and subscriptions to support the presenter.']}], 'duration': 517.7, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/-zI4mrF2Pb4/pics/-zI4mrF2Pb4487649.jpg', 'highlights': ['The time complexity of the algorithm is n cross m, and the worst-case backtracking time complexity is n plus m, making it an efficient solution for finding the longest common subsequence (LCS) of two strings.', 'The process involves checking for matches between characters in the two strings, determining the maximum length of the common subsequence, and efficiently backtracking to find the LCS, ensuring simplicity and straightforwardness in the code implementation.', 'The algorithm involves using a 2D array for tabulation, and the time complexity for backtracking is n plus m in the worst case, providing a comprehensive understanding of the process and the associated complexities.']}], 'highlights': ['The formula dp of i, j is equal to 1 + dp of i - 1 and j - 1, used when s of i - 1 is equal to s of 2j - 1. 5', 'The condition for dp of i, j is the maximum of dp of i - 1, j and dp of i, j - 1, selecting either the value from the previous row or the previous column. 4', 'The process involves comparing variables E and K to determine if they match, and filling up DP of 5 and 5 with a maximum value of 3. 3', "The process of retrieving and storing values is demonstrated using the example of matching 'E' elements, with the explanation of how the value is retrieved and written in the new position. 2", 'The concept of matching elements and the process of finding the maximum and storing the matches is explained using a step-by-step example, emphasizing the iterative movement and value comparisons. 1', 'The time complexity of the algorithm is n cross m, and the worst-case backtracking time complexity is n plus m, making it an efficient solution for finding the longest common subsequence (LCS) of two strings. 1', 'The process involves checking for matches between characters in the two strings, determining the maximum length of the common subsequence, and efficiently backtracking to find the LCS, ensuring simplicity and straightforwardness in the code implementation. 1', 'The algorithm involves using a 2D array for tabulation, and the time complexity for backtracking is n plus m in the worst case, providing a comprehensive understanding of the process and the associated complexities. 1', 'Covers techniques such as memoization, tabulation, and space optimization for solving the longest common subsequence problem. 1', 'Demonstrates finding the length of the longest common subsequence, which is 3 in the given example. 1', "Shows how to find the actual string of the longest common subsequence, which is 'BDE' in the given example. 1", 'The chapter explains the process of dynamic programming summation and tabulation, including the demonstration of creating and printing a DP array, which resulted in an answer of 3. 1', "The longest common subsequence (LCS) length of 'BD' in the strings 'ABCD' and 'abcd' is 2, thereby the DP array stores the value 2 at index (4, 2). 1", 'The string s1 has a length of 5, represented by the characters a, b, c, d, e. 1']}