title
DP 32. Distinct Subsequences | 1D Array Optimisation Technique 🔥

description
Lecture Notes/C++/Java Codes: https://takeuforward.org/dynamic-programming/striver-dp-series-dynamic-programming-problems/ Problem Link: https://bit.ly/3nZNxy7 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 distinct subsequences problems, which is a pattern in DP on Strings. Here we learn how to match strings. 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 32. Distinct Subsequences | 1D Array Optimisation Technique 🔥', 'heatmap': [{'end': 1041.976, 'start': 988.126, 'weight': 0.734}, {'end': 1332.735, 'start': 1303.176, 'weight': 1}, {'end': 1522.918, 'start': 1494.717, 'weight': 0.789}, {'end': 1620.264, 'start': 1567.05, 'weight': 0.709}, {'end': 1816.007, 'start': 1785.862, 'weight': 0.762}, {'end': 1860.638, 'start': 1834.714, 'weight': 0.707}, {'end': 1958.944, 'start': 1930.395, 'weight': 0.793}, {'end': 2345.556, 'start': 2316.083, 'weight': 0.737}], 'summary': 'Covers dynamic programming on strings, addressing distinct subsequences problem, recursion, string matching algorithm, tabulation technique, and code optimization, with a guarantee of simplification after solving three leetcode hard problems and successful code performance improvement.', 'chapters': [{'end': 171.701, 'segs': [{'end': 80.485, 'src': 'embed', 'start': 25.679, 'weight': 0, 'content': [{'end': 34.285, 'text': 'where we generally do something similar to matching, and we will be doing three problems, and all of these three problems will be lead code,', 'start': 25.679, 'duration': 8.606}, {'end': 34.986, 'text': 'hard version.', 'start': 34.285, 'duration': 0.701}, {'end': 43.869, 'text': 'yes, all of these three problems will be leetcode hard, and I can guarantee you that after this, DP on strings will look very, very simple to you.', 'start': 34.986, 'duration': 8.883}, {'end': 44.949, 'text': 'so what is the problem?', 'start': 43.869, 'duration': 1.08}, {'end': 47.47, 'text': 'it states distinct sub sequences.', 'start': 44.949, 'duration': 2.521}, {'end': 51.172, 'text': "okay. so the first problem states you're given a string, and what is the string?", 'start': 47.47, 'duration': 3.702}, {'end': 54.094, 'text': 'b, a, b, g, b, a, g?', 'start': 51.852, 'duration': 2.242}, {'end': 56.656, 'text': "and you're given another string, bank.", 'start': 54.094, 'duration': 2.562}, {'end': 63.822, 'text': 'okay, so you have to tell me, how many times does the string two appears in the string one.', 'start': 56.656, 'duration': 7.166}, {'end': 75.372, 'text': 'for an example, i can say b, a, or, if i use some other colors, b, a, b, then g and then b, a, g.', 'start': 63.822, 'duration': 11.55}, {'end': 80.485, 'text': 'so this this entire string, the yellow color, is the string s2.', 'start': 75.372, 'duration': 5.113}], 'summary': 'Solving 3 leetcode hard problems on distinct sub sequences, making dp on strings simpler.', 'duration': 54.806, 'max_score': 25.679, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/nVG7eTiD2bY/pics/nVG7eTiD2bY25679.jpg'}, {'end': 163.797, 'src': 'embed', 'start': 134.002, 'weight': 1, 'content': [{'end': 137.205, 'text': 'obviously we have to apply something like recursion.', 'start': 134.002, 'duration': 3.203}, {'end': 139.186, 'text': 'now, why do we apply recursion?', 'start': 137.205, 'duration': 1.981}, {'end': 141.908, 'text': 'and why not simple magic?', 'start': 139.186, 'duration': 2.722}, {'end': 147.15, 'text': 'because what i can say is, if i have a bag, if i have a bag like, how do i approach this problem?', 'start': 141.908, 'duration': 5.242}, {'end': 152.212, 'text': "my generic point of view will be let's take a bag and let's try to compare.", 'start': 147.15, 'duration': 5.062}, {'end': 158.115, 'text': 'okay, b, b gets compared, a, a gets compared, next, g gets compared over here, so that that will be one occurrence.', 'start': 152.212, 'duration': 5.903}, {'end': 163.797, 'text': 'But you could have said I will not compare G, this G, and I will compare this G with this G.', 'start': 158.675, 'duration': 5.122}], 'summary': 'Recursion is used for comparison in a bag, avoiding simple magic.', 'duration': 29.795, 'max_score': 134.002, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/nVG7eTiD2bY/pics/nVG7eTiD2bY134002.jpg'}], 'start': 0.302, 'title': 'Distinct subsequences problem', 'summary': 'Discusses the distinct subsequences problem in dynamic programming on strings, presenting a problem statement and explaining the approach to solving it using recursion, with a guarantee that after solving three leetcode hard problems, dynamic programming on strings will appear simpler.', 'chapters': [{'end': 171.701, 'start': 0.302, 'title': 'Distinct subsequences problem', 'summary': 'Discusses the distinct subsequences problem in dynamic programming on strings, presenting a problem statement and explaining the approach to solving it using recursion, with a guarantee that after solving three leetcode hard problems, dynamic programming on strings will appear simpler.', 'duration': 171.399, 'highlights': ['The chapter guarantees that after solving three LeetCode hard problems, dynamic programming on strings will appear simpler.', 'The problem statement is about finding the number of times a given string appears in another given string.', 'Explanation of the approach to solving the problem using recursion and comparison of characters for occurrences.']}], 'duration': 171.399, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/nVG7eTiD2bY/pics/nVG7eTiD2bY302.jpg', 'highlights': ['The problem statement is about finding the number of times a given string appears in another given string.', 'Explanation of the approach to solving the problem using recursion and comparison of characters for occurrences.', 'The chapter guarantees that after solving three LeetCode hard problems, dynamic programming on strings will appear simpler.']}, {'end': 388.515, 'segs': [{'end': 273.095, 'src': 'embed', 'start': 219.55, 'weight': 0, 'content': [{'end': 224.273, 'text': 'stating? It states count the number of ways.', 'start': 219.55, 'duration': 4.723}, {'end': 230.782, 'text': 'back to the recursion classes, lecture 6 and lecture 7.', 'start': 226.499, 'duration': 4.283}, {'end': 237.247, 'text': 'in recursion, whenever there is something like count and ways, what do you think?', 'start': 230.782, 'duration': 6.465}, {'end': 238.628, 'text': 'what do you think?', 'start': 237.247, 'duration': 1.381}, {'end': 241.75, 'text': "let's write down the pattern.", 'start': 238.628, 'duration': 3.122}, {'end': 245.173, 'text': "it's generally a function, which is the recursive function.", 'start': 241.75, 'duration': 3.423}, {'end': 250.274, 'text': 'the base case tends to return 1 or tends to return 0,', 'start': 245.173, 'duration': 5.101}, {'end': 256.485, 'text': "because you're counting the ways and you call all the functions and you add up them and you return.", 'start': 250.274, 'duration': 6.211}, {'end': 261.668, 'text': 'is what you do whenever the problem is count ways.', 'start': 258.007, 'duration': 3.661}, {'end': 266.071, 'text': 'remember this whenever the problem is count ways, you write a function.', 'start': 261.668, 'duration': 4.403}, {'end': 271.254, 'text': 'you know the base case has to return one or has to return zero, and then you try out.', 'start': 266.071, 'duration': 5.183}, {'end': 273.095, 'text': 'this is one of the possible ways.', 'start': 271.254, 'duration': 1.841}], 'summary': 'Recursion: count ways using recursive function with base case returning 1 or 0.', 'duration': 53.545, 'max_score': 219.55, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/nVG7eTiD2bY/pics/nVG7eTiD2bY219550.jpg'}, {'end': 388.515, 'src': 'embed', 'start': 293.764, 'weight': 3, 'content': [{'end': 298.565, 'text': 'how do i write the recurrence?', 'start': 293.764, 'duration': 4.801}, {'end': 302.426, 'text': 'okay, so what did i tell you in terms of strings over here?', 'start': 298.565, 'duration': 3.861}, {'end': 304.247, 'text': 'how many strings we have?', 'start': 302.426, 'duration': 1.821}, {'end': 306.748, 'text': 'we definitely have, uh, two strings.', 'start': 304.247, 'duration': 2.501}, {'end': 314.15, 'text': "whenever there are two strings, I've told you clearly that we are going to use two parameters.", 'start': 307.888, 'duration': 6.262}, {'end': 319.171, 'text': 'one parameter will be I, which represents the index in s1.', 'start': 314.15, 'duration': 5.021}, {'end': 323.753, 'text': 'the another parameter will be J, which represents the index in s2.', 'start': 319.171, 'duration': 4.582}, {'end': 338.377, 'text': 'so I can say the first step of writing the recurrence is very simple express, yes, I repeat, express everything in terms of i,', 'start': 323.753, 'duration': 14.624}, {'end': 342.158, 'text': 'which is the first string, and j, right.', 'start': 338.377, 'duration': 3.781}, {'end': 348.1, 'text': 'or the second thing explore all possibilities.', 'start': 342.158, 'duration': 5.942}, {'end': 353.679, 'text': 'and the third thing is count, always.', 'start': 350.518, 'duration': 3.161}, {'end': 356.76, 'text': 'so, return the summation of all possibilities.', 'start': 353.679, 'duration': 3.081}, {'end': 362.642, 'text': 'return the summation of all possibilities.', 'start': 356.76, 'duration': 5.882}, {'end': 367.044, 'text': 'and i can say the fourth step is very simple write down the base case.', 'start': 362.642, 'duration': 4.402}, {'end': 369.604, 'text': 'that is something which we always do and call it as a step.', 'start': 367.044, 'duration': 2.56}, {'end': 370.565, 'text': 'or you cannot.', 'start': 369.604, 'duration': 0.961}, {'end': 374.726, 'text': 'so if you, if you do all these steps, i think we will be pretty much done.', 'start': 370.565, 'duration': 4.161}, {'end': 382.55, 'text': "so what i do initially is i write f of i, j, as usual, And I'll keep the base case for the future.", 'start': 374.726, 'duration': 7.824}, {'end': 388.515, 'text': 'But as of now, I will try to write I and J is what we will try to write.', 'start': 382.59, 'duration': 5.925}], 'summary': 'Use two parameters i and j to express and count all possibilities in the recurrence for two strings, then write down the base case to complete the process.', 'duration': 94.751, 'max_score': 293.764, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/nVG7eTiD2bY/pics/nVG7eTiD2bY293764.jpg'}], 'start': 171.701, 'title': 'Recursion in counting ways and writing recurrence for strings', 'summary': 'Discusses the concept of recursion in counting ways and writing a recurrence for strings, emphasizing the need for different methodologies, the process of writing recursive functions, use of two parameters, expressing everything in terms of i and j, exploring all possibilities, and returning the summation of all possibilities, as taught in lecture 6 and 7 of the recursion playlist. it concludes with writing down the base case.', 'chapters': [{'end': 293.764, 'start': 171.701, 'title': 'Recursion in counting ways', 'summary': 'Discusses the concept of recursion in counting ways, emphasizing the need for different methodologies and explaining the process of writing recursive functions to count the number of ways, as taught in lecture 6 and 7 of the recursion playlist.', 'duration': 122.063, 'highlights': ['The process of counting ways involves trying different methodologies and using recursion to sum up all the ways, as explained in lecture 6 and 7 of the recursion playlist.', 'When dealing with problems related to counting ways, it is essential to write a recursive function with a base case that returns 1 or 0, and then try out different possible ways, summing up all the states and returning the result.', 'Understanding the concept of recursion in counting ways is crucial for writing the recurrence and effectively solving related problems.']}, {'end': 388.515, 'start': 293.764, 'title': 'Writing recurrence for strings', 'summary': 'Discusses writing a recurrence for strings, emphasizing the use of two parameters, expressing everything in terms of i and j, exploring all possibilities, and returning the summation of all possibilities, concluding with writing down the base case.', 'duration': 94.751, 'highlights': ['Emphasize using two parameters, I and J, to represent the indices in the two strings, as mentioned in the strategy for dealing with two strings.', 'Express everything in terms of i and j, explore all possibilities, and count the summation of all possibilities to form the recurrence.', 'Write down the base case as the final step in the process of writing the recurrence for the strings.']}], 'duration': 216.814, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/nVG7eTiD2bY/pics/nVG7eTiD2bY171701.jpg', 'highlights': ['The process of counting ways involves trying different methodologies and using recursion to sum up all the ways, as explained in lecture 6 and 7 of the recursion playlist.', 'Understanding the concept of recursion in counting ways is crucial for writing the recurrence and effectively solving related problems.', 'When dealing with problems related to counting ways, it is essential to write a recursive function with a base case that returns 1 or 0, and then try out different possible ways, summing up all the states and returning the result.', 'Emphasize using two parameters, I and J, to represent the indices in the two strings, as mentioned in the strategy for dealing with two strings.', 'Express everything in terms of i and j, explore all possibilities, and count the summation of all possibilities to form the recurrence.', 'Write down the base case as the final step in the process of writing the recurrence for the strings.']}, {'end': 845.673, 'segs': [{'end': 524.461, 'src': 'embed', 'start': 457.957, 'weight': 0, 'content': [{'end': 471.664, 'text': 'number of distinct subsequences between of, or you can say of string s2 from 0 to this, is i.', 'start': 457.957, 'duration': 13.707}, {'end': 481.779, 'text': "this is j, 0 to j in string s1, 0 to i, which means which means, let's go back,", 'start': 471.664, 'duration': 10.115}, {'end': 488.607, 'text': "which means you're saying this is so number of subsequences of bag in this entire string.", 'start': 481.779, 'duration': 6.828}, {'end': 498.356, 'text': 'if, if i was over here and j was over here, the number of subsequences of bag in this particular string because i is here,', 'start': 488.607, 'duration': 9.749}, {'end': 502.096, 'text': 'so i basically signifies that this much is the string.', 'start': 498.356, 'duration': 3.74}, {'end': 502.736, 'text': 'got it.', 'start': 502.096, 'duration': 0.64}, {'end': 507.957, 'text': 'so that is what we are writing f of i j, number of subsequences from 0 to j.', 'start': 502.736, 'duration': 5.221}, {'end': 512.918, 'text': 'like this is the string s2 in the string only from 0 to i.', 'start': 507.957, 'duration': 4.961}, {'end': 514.879, 'text': 'that is what it means.', 'start': 512.918, 'duration': 1.961}, {'end': 518.179, 'text': 'i hope you have understood the definition of f of i j.', 'start': 514.879, 'duration': 3.3}, {'end': 520.38, 'text': 'what are we trying to explain by f of i j?', 'start': 518.179, 'duration': 2.201}, {'end': 524.461, 'text': 'okay, next, so we have written this and we have understood.', 'start': 521.02, 'duration': 3.441}], 'summary': 'Explaining the number of subsequences in a string.', 'duration': 66.504, 'max_score': 457.957, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/nVG7eTiD2bY/pics/nVG7eTiD2bY457957.jpg'}, {'end': 586.42, 'src': 'embed', 'start': 557.55, 'weight': 2, 'content': [{'end': 560.012, 'text': 'so you can be like he is tribal.', 'start': 557.55, 'duration': 2.462}, {'end': 560.472, 'text': "they're matching.", 'start': 560.012, 'duration': 0.46}, {'end': 567.166, 'text': "So this can be the G, because for this G I'm looking for a G in S1..", 'start': 561.502, 'duration': 5.664}, {'end': 569.728, 'text': "Let's understand what are we trying to do.", 'start': 567.346, 'duration': 2.382}, {'end': 570.549, 'text': "Let's understand this.", 'start': 569.808, 'duration': 0.741}, {'end': 573.991, 'text': "What am I trying to do? I'm trying to figure this bag out.", 'start': 571.009, 'duration': 2.982}, {'end': 577.073, 'text': 'How many times does this bag occur over here?', 'start': 574.832, 'duration': 2.241}, {'end': 582.037, 'text': "For that, what I'm trying to do is I'm tweaking this G and I'm saying okay, this is the G.", 'start': 577.614, 'duration': 4.423}, {'end': 582.977, 'text': 'this is the G.', 'start': 582.037, 'duration': 0.94}, {'end': 585.059, 'text': "Where's the A? This is the A.", 'start': 582.977, 'duration': 2.082}, {'end': 586.42, 'text': "Where's the B? This is the B.", 'start': 585.059, 'duration': 1.361}], 'summary': 'Trying to figure out occurrences of the bag by tweaking g, a, and b.', 'duration': 28.87, 'max_score': 557.55, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/nVG7eTiD2bY/pics/nVG7eTiD2bY557550.jpg'}, {'end': 824.033, 'src': 'embed', 'start': 794.301, 'weight': 1, 'content': [{'end': 796.942, 'text': 'You have to reduce the string in order to do the search.', 'start': 794.301, 'duration': 2.641}, {'end': 802.704, 'text': "So, I can say, okay, what if they're not matching? Because that might be a case in future.", 'start': 797.322, 'duration': 5.382}, {'end': 809.005, 'text': "So, if that's the case, I'll be like, I'll reduce the first string and I'll still keep on searching.", 'start': 803.264, 'duration': 5.741}, {'end': 810.026, 'text': 'Okay, makes sense.', 'start': 809.446, 'duration': 0.58}, {'end': 814.867, 'text': "So, I've understood if they're matching, if they're matching, there can be two states.", 'start': 810.706, 'duration': 4.161}, {'end': 816.348, 'text': 'One is this, one is this.', 'start': 815.067, 'duration': 1.281}, {'end': 821.371, 'text': "if they are not matching, then i'll reduce and look for somewhere else.", 'start': 817.248, 'duration': 4.123}, {'end': 824.033, 'text': 'so these are two different states.', 'start': 821.371, 'duration': 2.662}], 'summary': 'The process involves reducing strings for search, handling matching and non-matching cases, and identifying two different states.', 'duration': 29.732, 'max_score': 794.301, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/nVG7eTiD2bY/pics/nVG7eTiD2bY794301.jpg'}], 'start': 389.055, 'title': 'Understanding subsequences, bag occurrences, and string matching algorithm', 'summary': 'Explains subsequences in strings with the example of bap and back, discusses bag occurrence analysis, and outlines a string matching algorithm. it details the calculation of distinct subsequences, permutations in bag occurrences, and iterative reduction and search in string matching.', 'chapters': [{'end': 557.55, 'start': 389.055, 'title': 'Understanding subsequences in strings', 'summary': 'Explains the concept of subsequences in strings using the example of strings bap and back, detailing the calculation of number of distinct subsequences with i and j indices.', 'duration': 168.495, 'highlights': ['The chapter explains the concept of subsequences in strings using the example of strings BAP and back, detailing the calculation of number of distinct subsequences with i and j indices.', 'The speaker breaks down the meaning of f of i j, representing the number of subsequences from 0 to j in string s2 in the string only from 0 to i, providing a clear understanding of the definition and purpose of f of i j.', 'The discussion delves into exploring all possibilities, using the example of matching characters in strings, to further illustrate the concept of subsequences.']}, {'end': 651.967, 'start': 557.55, 'title': 'Bag occurrence analysis', 'summary': 'Discusses the process of analyzing bag occurrences and the different permutations and combinations involved in identifying occurrences, aiming to find the total number of bag occurrences.', 'duration': 94.417, 'highlights': ["The process involves identifying different combinations of 'G', 'A', and 'B' to count bag occurrences.", "The speaker explains various permutations of 'G', 'A', and 'B' and the different combinations that lead to bag occurrences.", 'The speaker emphasizes the importance of matching patterns and outlines the steps involved in identifying bag occurrences.']}, {'end': 845.673, 'start': 651.967, 'title': 'String matching algorithm', 'summary': 'Outlines a string matching algorithm using iterative reduction and search, detailing the process of comparing and reducing strings to find matches, with an emphasis on exploring all possible states and outcomes.', 'duration': 193.706, 'highlights': ["By iteratively reducing and searching the string, it is possible to find matches and explore all possibilities, leading to a comprehensive understanding of the algorithm's behavior.", 'The process involves comparing and reducing strings to find matches, with specific examples of how to handle cases where matching is not immediately achieved.', 'Exploring all possible states and outcomes is a key emphasis of the algorithm, ensuring a thorough understanding of the matching process and potential results.']}], 'duration': 456.618, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/nVG7eTiD2bY/pics/nVG7eTiD2bY389055.jpg', 'highlights': ['The chapter explains the concept of subsequences in strings using the example of strings BAP and back, detailing the calculation of number of distinct subsequences with i and j indices.', "By iteratively reducing and searching the string, it is possible to find matches and explore all possibilities, leading to a comprehensive understanding of the algorithm's behavior.", "The process involves identifying different combinations of 'G', 'A', and 'B' to count bag occurrences.", 'The speaker breaks down the meaning of f of i j, representing the number of subsequences from 0 to j in string s2 in the string only from 0 to i, providing a clear understanding of the definition and purpose of f of i j.']}, {'end': 1370.192, 'segs': [{'end': 1056.143, 'src': 'heatmap', 'start': 988.126, 'weight': 3, 'content': [{'end': 990.346, 'text': 'So can I say the first base case is very simple.', 'start': 988.126, 'duration': 2.22}, {'end': 995.568, 'text': "If I have matched all characters of the string S2, there's no thinking.", 'start': 991.267, 'duration': 4.301}, {'end': 998.703, 'text': 'Go across and return 1.', 'start': 996.568, 'duration': 2.135}, {'end': 1011.926, 'text': 'But if this did not happen, and I exhaust the first string and I exhaust the first string, so there is still matching to be done on the J counterpart.', 'start': 998.703, 'duration': 13.223}, {'end': 1014.507, 'text': 'There is still some matching to be done on J counterpart.', 'start': 1012.186, 'duration': 2.321}, {'end': 1017.808, 'text': 'So I will go across and return a zero.', 'start': 1014.987, 'duration': 2.821}, {'end': 1018.588, 'text': "That's it.", 'start': 1018.248, 'duration': 0.34}, {'end': 1020.408, 'text': "That's how you write the base cases.", 'start': 1018.988, 'duration': 1.42}, {'end': 1023.349, 'text': 'As simple as it could have got.', 'start': 1021.428, 'duration': 1.921}, {'end': 1031.972, 'text': 'So we have written the recursion, right? And how many states are there? There are definitely two states.', 'start': 1024.969, 'duration': 7.003}, {'end': 1041.976, 'text': 'And I know the time complexity of this recursion, if I ask you, will go exponential.', 'start': 1032.791, 'duration': 9.185}, {'end': 1049.658, 'text': 'Assuming you are doing all type of comparisons, there can be a lot of comparisons.', 'start': 1044.614, 'duration': 5.044}, {'end': 1056.143, 'text': 'Somewhere near about 2 to the power n will be the number of subsequences of string S1.', 'start': 1050.198, 'duration': 5.945}], 'summary': 'Recursive function with 2 states, time complexity exponential, 2^n subsequences of string s1', 'duration': 64.876, 'max_score': 988.126, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/nVG7eTiD2bY/pics/nVG7eTiD2bY988126.jpg'}, {'end': 1137.076, 'src': 'embed', 'start': 1107.77, 'weight': 1, 'content': [{'end': 1116.314, 'text': 'and I am not drawing it because this is the 30 second lecture of the dynamic programming series and I have been telling this all over overlapping sub-problems.', 'start': 1107.77, 'duration': 8.544}, {'end': 1118.155, 'text': "So there is no way I'm doing that.", 'start': 1117.115, 'duration': 1.04}, {'end': 1121.577, 'text': 'Okay, so what do you do? A very simple memory action.', 'start': 1118.676, 'duration': 2.901}, {'end': 1123.909, 'text': 'how do you memorize?', 'start': 1122.768, 'duration': 1.141}, {'end': 1130.632, 'text': 'what are the changing parameters i j, how much is i n?', 'start': 1123.909, 'duration': 6.723}, {'end': 1132.553, 'text': 'how much is j m?', 'start': 1130.632, 'duration': 1.921}, {'end': 1134.735, 'text': 'so n cross m dp?', 'start': 1132.553, 'duration': 2.182}, {'end': 1137.076, 'text': 'yeah, how do you do this?', 'start': 1134.735, 'duration': 2.341}], 'summary': '30-second dynamic programming lecture emphasizes memorization and changing parameters for n x m dp.', 'duration': 29.306, 'max_score': 1107.77, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/nVG7eTiD2bY/pics/nVG7eTiD2bY1107770.jpg'}, {'end': 1336.356, 'src': 'heatmap', 'start': 1297.972, 'weight': 0, 'content': [{'end': 1303.176, 'text': "and see if this works fine or gives TLE, because it's the memoization code.", 'start': 1297.972, 'duration': 5.204}, {'end': 1305.939, 'text': 'as usual, it did give us the time limit exceeded.', 'start': 1303.176, 'duration': 2.763}, {'end': 1310.322, 'text': 'why? because we are using the memoization technique over here.', 'start': 1305.939, 'duration': 4.383}, {'end': 1314.826, 'text': 'we need to use the tabulation in order to remove this time limit exceeded.', 'start': 1310.322, 'duration': 4.504}, {'end': 1316.608, 'text': "so let's go and check out the tabulation method.", 'start': 1314.826, 'duration': 1.782}, {'end': 1321.03, 'text': 'So, as you saw, the memoization technique did give you time limit exceeded right?', 'start': 1317.088, 'duration': 3.942}, {'end': 1326.412, 'text': 'So obviously we need to remove this auxiliary stack space and the recursion calls that we are making.', 'start': 1321.43, 'duration': 4.982}, {'end': 1332.735, 'text': 'And in order to do that, what we can do this is we can definitely apply tabulation right?', 'start': 1326.952, 'duration': 5.783}, {'end': 1336.356, 'text': 'What is the first rule of tabulation?', 'start': 1335.076, 'duration': 1.28}], 'summary': 'Memoization technique causing tle, switching to tabulation for optimization.', 'duration': 38.384, 'max_score': 1297.972, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/nVG7eTiD2bY/pics/nVG7eTiD2bY1297972.jpg'}, {'end': 1370.192, 'src': 'embed', 'start': 1339.137, 'weight': 2, 'content': [{'end': 1342.599, 'text': 'So just go across and declare the same size of DP array.', 'start': 1339.137, 'duration': 3.462}, {'end': 1346.832, 'text': 'Done Then write down the base cases.', 'start': 1343.039, 'duration': 3.793}, {'end': 1356.14, 'text': 'So, and then write down the changing parameters in the opposite fashion.', 'start': 1350.475, 'duration': 5.665}, {'end': 1360.283, 'text': 'And then copy paste the recurrence.', 'start': 1357.181, 'duration': 3.102}, {'end': 1363.766, 'text': 'Is that what you do? Yes, that is what you do.', 'start': 1361.144, 'duration': 2.622}, {'end': 1365.788, 'text': 'Just write it across.', 'start': 1364.587, 'duration': 1.201}, {'end': 1370.192, 'text': 'So write down the base cases is what you have to do.', 'start': 1366.349, 'duration': 3.843}], 'summary': 'Process for writing dynamic programming algorithm: declare array, base cases, changing parameters, recurrence.', 'duration': 31.055, 'max_score': 1339.137, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/nVG7eTiD2bY/pics/nVG7eTiD2bY1339137.jpg'}], 'start': 846.174, 'title': 'Counting ways and tabulation technique', 'summary': 'Discusses base cases and optimization for counting ways, addressing exponential time complexity and space complexity issues, and the implementation of tabulation technique for string matching to optimize the code and remove time limit exceeded issues.', 'chapters': [{'end': 1168.706, 'start': 846.174, 'title': 'Counting ways: base cases and optimization', 'summary': 'Discusses the base cases for counting ways, determining the return values of 1 and 0 based on string matches, and the optimization of the solution through memorization to address the exponential time complexity and space complexity issues.', 'duration': 322.532, 'highlights': ['The base cases involve returning 1 when all characters of string S2 match, and returning 0 when the first string is exhausted and there is still matching to be done on the J counterpart.', 'The time complexity of the recursion is exponential, approximately 2 to the power n for the number of subsequences of string S1 and 2 to the power m for string S2.', 'The space complexity can be optimized through memorization, using a simple memory action with changing parameters i and j, resulting in a ready memorization solution.']}, {'end': 1370.192, 'start': 1168.706, 'title': 'Tabulation technique for string matching', 'summary': 'Discusses the implementation of the tabulation technique for string matching, demonstrating the transition from memoization to tabulation in order to optimize the code and remove time limit exceeded issues, and also explains the key steps involved in the process.', 'duration': 201.486, 'highlights': ['The memoization technique initially led to time limit exceeded as it used auxiliary stack space and recursive calls, prompting the need to transition to tabulation for optimizing the code.', 'The process involves declaring an identical DP array, setting the base cases, arranging the changing parameters in reverse order, and replicating the recurrence to efficiently implement tabulation.', 'The code optimization resulted in improved performance, eliminating the time limit exceeded issue and ensuring efficient string matching operations.']}], 'duration': 524.018, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/nVG7eTiD2bY/pics/nVG7eTiD2bY846174.jpg', 'highlights': ['The code optimization resulted in improved performance, eliminating the time limit exceeded issue and ensuring efficient string matching operations.', 'The space complexity can be optimized through memorization, using a simple memory action with changing parameters i and j, resulting in a ready memorization solution.', 'The process involves declaring an identical DP array, setting the base cases, arranging the changing parameters in reverse order, and replicating the recurrence to efficiently implement tabulation.', 'The base cases involve returning 1 when all characters of string S2 match, and returning 0 when the first string is exhausted and there is still matching to be done on the J counterpart.', 'The memoization technique initially led to time limit exceeded as it used auxiliary stack space and recursive calls, prompting the need to transition to tabulation for optimizing the code.', 'The time complexity of the recursion is exponential, approximately 2 to the power n for the number of subsequences of string S1 and 2 to the power m for string S2.']}, {'end': 1890.694, 'segs': [{'end': 1395.179, 'src': 'embed', 'start': 1370.832, 'weight': 2, 'content': [{'end': 1380.032, 'text': 'But do you remember LCS?, where we did something like one based indexing?', 'start': 1370.832, 'duration': 9.2}, {'end': 1382.933, 'text': "in case you don't know, please follow the db playlist.", 'start': 1380.032, 'duration': 2.901}, {'end': 1390.397, 'text': 'so, over here, yes, over here we are writing something as j less than zero and i less than zero.', 'start': 1382.933, 'duration': 7.464}, {'end': 1395.179, 'text': 'so what we are doing basically is we are, as of now, dealing with zero based indexing.', 'start': 1390.397, 'duration': 4.782}], 'summary': 'Discussion about transitioning from one-based indexing to zero-based indexing in lcs algorithm.', 'duration': 24.347, 'max_score': 1370.832, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/nVG7eTiD2bY/pics/nVG7eTiD2bY1370832.jpg'}, {'end': 1438.183, 'src': 'embed', 'start': 1413.488, 'weight': 1, 'content': [{'end': 1420.311, 'text': 'so in order to yes, in order to deal with it, what we will do is we will just add a plus one to everything that we are doing.', 'start': 1413.488, 'duration': 6.823}, {'end': 1423.233, 'text': "we'll just add a plus 1 to everything we are doing.", 'start': 1420.751, 'duration': 2.482}, {'end': 1425.194, 'text': 'we were calling by n minus 1.', 'start': 1423.233, 'duration': 1.961}, {'end': 1429.217, 'text': 'what we will do is we will call it with n, we will call it with n.', 'start': 1425.194, 'duration': 4.023}, {'end': 1438.183, 'text': 'okay. and over here, since we did a plus 1, now we know one thing for sure this will not be lesser than equal to instead of this.', 'start': 1429.217, 'duration': 8.966}], 'summary': 'Adjusting by adding plus one to all values, including n, to ensure not lesser than or equal to.', 'duration': 24.695, 'max_score': 1413.488, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/nVG7eTiD2bY/pics/nVG7eTiD2bY1413488.jpg'}, {'end': 1488.794, 'src': 'embed', 'start': 1459.311, 'weight': 0, 'content': [{'end': 1460.151, 'text': "So that's one lesser.", 'start': 1459.311, 'duration': 0.84}, {'end': 1461.676, 'text': "That's one lesson.", 'start': 1461.055, 'duration': 0.621}, {'end': 1470.402, 'text': 'So over here, instead of this, you write S1 of I minus 1 equal to equal to S2 of J minus 1.', 'start': 1462.036, 'duration': 8.366}, {'end': 1472.404, 'text': 'You just compare the previous guys.', 'start': 1470.402, 'duration': 2.002}, {'end': 1472.744, 'text': "That's it.", 'start': 1472.444, 'duration': 0.3}, {'end': 1476.087, 'text': 'And I think apart from that, everything stays as it is.', 'start': 1473.445, 'duration': 2.642}, {'end': 1478.189, 'text': 'You carry on one-way indexing.', 'start': 1476.567, 'duration': 1.622}, {'end': 1479.529, 'text': 'when comparing.', 'start': 1478.809, 'duration': 0.72}, {'end': 1488.794, 'text': "just make sure you compare with zero base, because the strings are zero based, right, and once you've done this now you can easily write this off.", 'start': 1479.529, 'duration': 9.265}], 'summary': 'Using one-way indexing and comparing with zero base simplifies string comparison.', 'duration': 29.483, 'max_score': 1459.311, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/nVG7eTiD2bY/pics/nVG7eTiD2bY1459311.jpg'}, {'end': 1522.918, 'src': 'heatmap', 'start': 1494.717, 'weight': 0.789, 'content': [{'end': 1501.862, 'text': "okay, so what I'll do is I'll just do this minor changes, and just make sure you also declare the dp array of size 1 plus,", 'start': 1494.717, 'duration': 7.145}, {'end': 1506.506, 'text': 'because you did this minor changes and over here just do i minus 1 and a j minus 1.', 'start': 1501.862, 'duration': 4.644}, {'end': 1507.186, 'text': "that's it.", 'start': 1506.506, 'duration': 0.68}, {'end': 1514.291, 'text': 'and apart from that, everything will stay as it is and try to run this and you will see that this is definitely running fine.', 'start': 1507.186, 'duration': 7.105}, {'end': 1517.574, 'text': "it is, but i'll not submit it because, yeah, we know it will give tle.", 'start': 1514.291, 'duration': 3.283}, {'end': 1519.175, 'text': 'so we are not going to submit it.', 'start': 1517.574, 'duration': 1.601}, {'end': 1522.918, 'text': 'coming back to ipad okay, write down the base cases.', 'start': 1519.175, 'duration': 3.743}], 'summary': 'Make minor changes in code, declare dp array size 1+, adjust i-1 and j-1. not submitting due to tle.', 'duration': 28.201, 'max_score': 1494.717, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/nVG7eTiD2bY/pics/nVG7eTiD2bY1494717.jpg'}, {'end': 1620.264, 'src': 'heatmap', 'start': 1567.05, 'weight': 0.709, 'content': [{'end': 1572.133, 'text': "Because as long as the j is 0, I'm going to put a 1.", 'start': 1567.05, 'duration': 5.083}, {'end': 1573.454, 'text': "Doesn't matter what i is coming.", 'start': 1572.133, 'duration': 1.321}, {'end': 1574.735, 'text': 'And what is the other case?', 'start': 1574.094, 'duration': 0.641}, {'end': 1577.508, 'text': 'i equal to equal to zero.', 'start': 1575.766, 'duration': 1.742}, {'end': 1579.409, 'text': 'in this, you have to put a zero.', 'start': 1577.508, 'duration': 1.901}, {'end': 1582.191, 'text': "so that's going to be very simple.", 'start': 1579.409, 'duration': 2.782}, {'end': 1590.378, 'text': "for any j, for any j, you're going to say dp of 0, which is i, and for any j, it is going to be 0.", 'start': 1582.191, 'duration': 8.187}, {'end': 1592.26, 'text': "that's it.", 'start': 1590.378, 'duration': 1.882}, {'end': 1595.422, 'text': 'these are going to be your base cases.', 'start': 1592.26, 'duration': 3.162}, {'end': 1599.205, 'text': 'just look at the base cases and try to write them perfect.', 'start': 1595.422, 'duration': 3.783}, {'end': 1602.488, 'text': "so i've written the base cases step done.", 'start': 1599.205, 'duration': 3.283}, {'end': 1606.898, 'text': 'Next, write down the changing parameters.', 'start': 1604.597, 'duration': 2.301}, {'end': 1610.299, 'text': 'We definitely know the changing parameters are i and j.', 'start': 1607.078, 'duration': 3.221}, {'end': 1617.643, 'text': 'Where are the parameters changing? What did you do for i? From n to 0 is what you went.', 'start': 1610.299, 'duration': 7.344}, {'end': 1620.264, 'text': 'From m to 0 is what you went.', 'start': 1618.503, 'duration': 1.761}], 'summary': 'Setting base cases for dynamic programming with changing parameters i and j.', 'duration': 53.214, 'max_score': 1567.05, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/nVG7eTiD2bY/pics/nVG7eTiD2bY1567050.jpg'}, {'end': 1610.299, 'src': 'embed', 'start': 1582.191, 'weight': 3, 'content': [{'end': 1590.378, 'text': "for any j, for any j, you're going to say dp of 0, which is i, and for any j, it is going to be 0.", 'start': 1582.191, 'duration': 8.187}, {'end': 1592.26, 'text': "that's it.", 'start': 1590.378, 'duration': 1.882}, {'end': 1595.422, 'text': 'these are going to be your base cases.', 'start': 1592.26, 'duration': 3.162}, {'end': 1599.205, 'text': 'just look at the base cases and try to write them perfect.', 'start': 1595.422, 'duration': 3.783}, {'end': 1602.488, 'text': "so i've written the base cases step done.", 'start': 1599.205, 'duration': 3.283}, {'end': 1606.898, 'text': 'Next, write down the changing parameters.', 'start': 1604.597, 'duration': 2.301}, {'end': 1610.299, 'text': 'We definitely know the changing parameters are i and j.', 'start': 1607.078, 'duration': 3.221}], 'summary': 'Base cases: dp(0, i)=i, dp(i, 0)=0. changing parameters: i, j.', 'duration': 28.108, 'max_score': 1582.191, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/nVG7eTiD2bY/pics/nVG7eTiD2bY1582191.jpg'}, {'end': 1666.415, 'src': 'embed', 'start': 1638.68, 'weight': 4, 'content': [{'end': 1641.562, 'text': 'So, you go to the next, which is from 1 to n.', 'start': 1638.68, 'duration': 2.882}, {'end': 1644.223, 'text': 'You go to the next from j, which is from 1 to m.', 'start': 1641.562, 'duration': 2.661}, {'end': 1646.145, 'text': 'And then you copy paste the recurrence in between.', 'start': 1644.223, 'duration': 1.922}, {'end': 1649.887, 'text': "And the answer is at dp of nm, because that's what you call it.", 'start': 1646.785, 'duration': 3.102}, {'end': 1653.829, 'text': 'And if you do this, you indeed get your answer.', 'start': 1650.487, 'duration': 3.342}, {'end': 1660.533, 'text': "So, without actually waiting, let's get back and try to write this perfect tabulation code.", 'start': 1654.369, 'duration': 6.164}, {'end': 1666.415, 'text': 'So, what did we do? If you remember well, we just made sure this is 0, nothing else.', 'start': 1660.993, 'duration': 5.422}], 'summary': 'Iteratively solving recurrence yields answer at dp of nm.', 'duration': 27.735, 'max_score': 1638.68, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/nVG7eTiD2bY/pics/nVG7eTiD2bY1638680.jpg'}, {'end': 1816.007, 'src': 'heatmap', 'start': 1785.862, 'weight': 0.762, 'content': [{'end': 1793.425, 'text': "so just make sure that j actually starts from one instead of zero, because for this base case you can't rewrite the zero that you've written.", 'start': 1785.862, 'duration': 7.563}, {'end': 1795.425, 'text': "and now let's quickly try to run this.", 'start': 1793.425, 'duration': 2}, {'end': 1796.426, 'text': 'it does run.', 'start': 1795.425, 'duration': 1.001}, {'end': 1798.126, 'text': 'you can actually omit this as well.', 'start': 1796.426, 'duration': 1.7}, {'end': 1804.008, 'text': "why? because you're already initializing everything with zero, so you can omit this as well, and now you can try to submit this.", 'start': 1798.126, 'duration': 5.882}, {'end': 1806.74, 'text': 'okay, so we got a runtime error.', 'start': 1804.878, 'duration': 1.862}, {'end': 1808.881, 'text': "it's mostly because of the integer overflow.", 'start': 1806.74, 'duration': 2.141}, {'end': 1816.007, 'text': "you just make sure this has to be long, long like not sure why, because i think that's such a test case issue.", 'start': 1808.881, 'duration': 7.126}], 'summary': 'Code initializes from one, leading to runtime error due to integer overflow.', 'duration': 30.145, 'max_score': 1785.862, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/nVG7eTiD2bY/pics/nVG7eTiD2bY1785862.jpg'}, {'end': 1845.161, 'src': 'embed', 'start': 1817.528, 'weight': 5, 'content': [{'end': 1822.993, 'text': "so just make sure you just make everything as long long that's the best that you can do and try to run this off.", 'start': 1817.528, 'duration': 5.465}, {'end': 1827.849, 'text': 'okay, it does give the runtime error with these cases as well, okay.', 'start': 1822.993, 'duration': 4.856}, {'end': 1834.714, 'text': 'so mostly it is getting an overflow again, mostly because of the conversion error or something like this.', 'start': 1827.849, 'duration': 6.865}, {'end': 1845.161, 'text': "so generally what i tend to do is let's convert this into double and uh, we'll convert this into double and over here just do a typecast.", 'start': 1834.714, 'duration': 10.447}], 'summary': 'Troubleshooting for runtime error due to overflow, suggesting typecast to double.', 'duration': 27.633, 'max_score': 1817.528, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/nVG7eTiD2bY/pics/nVG7eTiD2bY1817528.jpg'}, {'end': 1860.638, 'src': 'heatmap', 'start': 1834.714, 'weight': 0.707, 'content': [{'end': 1845.161, 'text': "so generally what i tend to do is let's convert this into double and uh, we'll convert this into double and over here just do a typecast.", 'start': 1834.714, 'duration': 10.447}, {'end': 1846.662, 'text': "that's what we can do.", 'start': 1845.161, 'duration': 1.501}, {'end': 1848.764, 'text': "that's what i generally do in competitive programming.", 'start': 1846.662, 'duration': 2.102}, {'end': 1852.674, 'text': "Okay, now let's try to submit this and see if this runs.", 'start': 1849.892, 'duration': 2.782}, {'end': 1853.994, 'text': "That's how I will handle it.", 'start': 1852.894, 'duration': 1.1}, {'end': 1860.638, 'text': "I was giving it long, long, but eventually it will overflow and you can't typecast it back.", 'start': 1854.695, 'duration': 5.943}], 'summary': 'The speaker converts values to double for competitive programming and handles potential overflow issues.', 'duration': 25.924, 'max_score': 1834.714, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/nVG7eTiD2bY/pics/nVG7eTiD2bY1834714.jpg'}, {'end': 1890.694, 'src': 'embed', 'start': 1861.119, 'weight': 6, 'content': [{'end': 1864.781, 'text': 'So what I did was I just made it a double and then we converted it back.', 'start': 1861.119, 'duration': 3.662}, {'end': 1867.703, 'text': 'In Java, this will not throw a runtime error.', 'start': 1865.141, 'duration': 2.562}, {'end': 1872.205, 'text': 'So can we optimize this? Yes.', 'start': 1868.603, 'duration': 3.602}, {'end': 1876.348, 'text': "The space optimization technique that I've taught you from the last 32 lectures, you can.", 'start': 1872.545, 'duration': 3.803}, {'end': 1878.569, 'text': "Why? Let's see.", 'start': 1876.408, 'duration': 2.161}, {'end': 1885.745, 'text': 'i minus one, i minus one again an i minus one.', 'start': 1880.094, 'duration': 5.651}, {'end': 1887.969, 'text': "let's do a space optimization.", 'start': 1885.745, 'duration': 2.224}, {'end': 1890.694, 'text': "so you'll be like fine, i'll be like vector double.", 'start': 1887.969, 'duration': 2.725}], 'summary': 'Optimized space technique in java avoids runtime errors.', 'duration': 29.575, 'max_score': 1861.119, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/nVG7eTiD2bY/pics/nVG7eTiD2bY1861119.jpg'}], 'start': 1370.832, 'title': 'String comparison techniques', 'summary': 'Discusses handling negative indexing by adding a plus one to all indexes, and adjusting the comparison logic, and dynamic programming using tabulation for string comparison, emphasizing base cases, changing parameters, handling potential runtime errors, and space optimization.', 'chapters': [{'end': 1479.529, 'start': 1370.832, 'title': 'Handling negative indexing in string comparison', 'summary': 'Discusses the need to handle negative indexing in string comparison algorithms, where a plus one is added to all indexes to avoid negative values, and the comparison logic is adjusted accordingly, while still maintaining zero-based indexing.', 'duration': 108.697, 'highlights': ['The need to handle negative indexing in string comparison algorithms, which arises when dealing with exhausted string indexes, is highlighted. This is addressed by adding a plus one to all indexes to avoid negative values.', 'The adjustment of comparison logic to handle negative indexing, where the previous elements are compared using the modified indexes, is emphasized as a key modification in the algorithm.', 'The concept of one-based indexing being used initially, followed by the transition to zero-based indexing, is explained as a fundamental shift in the approach of the algorithm.']}, {'end': 1890.694, 'start': 1479.529, 'title': 'Dynamic programming for string comparison', 'summary': 'Discusses the technique of tabulation for dynamic programming with a focus on string comparison, emphasizing the need for base cases and changing parameters, while also addressing potential runtime errors and space optimization.', 'duration': 411.165, 'highlights': ['The chapter emphasizes the importance of defining base cases for string comparison, such as setting dp of i and 0 to 1 for any i and dp of 0 and j to 0 for any j.', 'The strategy of tabulation for dynamic programming is highlighted, involving iterating through the changing parameters i and j, and implementing the recurrence relation to find the answer at dp of nm.', 'The discussion addresses the identification and resolution of potential runtime errors, such as integer overflow, by converting data types and implementing typecasting to handle the issue.', 'The concept of space optimization technique for dynamic programming is introduced, with a focus on minimizing the space complexity by using a vector of type double.']}], 'duration': 519.862, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/nVG7eTiD2bY/pics/nVG7eTiD2bY1370832.jpg', 'highlights': ['The adjustment of comparison logic to handle negative indexing is emphasized as a key modification in the algorithm.', 'The need to handle negative indexing in string comparison algorithms is addressed by adding a plus one to all indexes to avoid negative values.', 'The concept of one-based indexing being used initially, followed by the transition to zero-based indexing, is explained as a fundamental shift in the approach of the algorithm.', 'The chapter emphasizes the importance of defining base cases for string comparison, such as setting dp of i and 0 to 1 for any i and dp of 0 and j to 0 for any j.', 'The strategy of tabulation for dynamic programming is highlighted, involving iterating through the changing parameters i and j, and implementing the recurrence relation to find the answer at dp of nm.', 'The discussion addresses the identification and resolution of potential runtime errors, such as integer overflow, by converting data types and implementing typecasting to handle the issue.', 'The concept of space optimization technique for dynamic programming is introduced, with a focus on minimizing the space complexity by using a vector of type double.']}, {'end': 2405.306, 'segs': [{'end': 1958.944, 'src': 'heatmap', 'start': 1909.646, 'weight': 0, 'content': [{'end': 1917.629, 'text': "let's store the previous rows value and similarly let's define a curve which stores the previous rows value again.", 'start': 1909.646, 'duration': 7.983}, {'end': 1919.41, 'text': 'okay. so what is this line doing?', 'start': 1917.629, 'duration': 1.781}, {'end': 1921.791, 'text': 'this line is basically going to every row.', 'start': 1919.41, 'duration': 2.381}, {'end': 1923.112, 'text': 'i means every row.', 'start': 1921.791, 'duration': 1.321}, {'end': 1930.395, 'text': 'it goes to uh row zero, row one, row two, and at every column zero it goes across and putting one.', 'start': 1923.112, 'duration': 7.283}, {'end': 1937.558, 'text': "since we're just dealing with uh, two columns, if you see two guys, one is previous and the other one is the current that you will be computing.", 'start': 1930.395, 'duration': 7.163}, {'end': 1942.479, 'text': 'So what you can do is in both of them, you can just put a cross of 1 at the 0th place.', 'start': 1938.118, 'duration': 4.361}, {'end': 1944.7, 'text': "Right? Let's go across and do this.", 'start': 1943.039, 'duration': 1.661}, {'end': 1950.741, 'text': 'Instead of this, you can say, okay, previous of 0 equal to curve of 0 is going to be 1.', 'start': 1945.54, 'duration': 5.201}, {'end': 1954.643, 'text': 'Amazing Over here, this means definitely previous.', 'start': 1950.741, 'duration': 3.902}, {'end': 1958.944, 'text': 'Again, this means definitely previous.', 'start': 1955.763, 'duration': 3.181}], 'summary': 'Storing and defining curves for previous row values, computing with 1s.', 'duration': 41.095, 'max_score': 1909.646, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/nVG7eTiD2bY/pics/nVG7eTiD2bY1909646.jpg'}, {'end': 2286.104, 'src': 'embed', 'start': 2243.816, 'weight': 1, 'content': [{'end': 2244.558, 'text': "that's what you're doing.", 'start': 2243.816, 'duration': 0.742}, {'end': 2247.102, 'text': "you're writing it on the previous itself.", 'start': 2244.558, 'duration': 2.544}, {'end': 2249.346, 'text': "you're writing it on the previous itself.", 'start': 2247.102, 'duration': 2.244}, {'end': 2252.471, 'text': 'so whatever is computed here, it goes on writing over here.', 'start': 2249.346, 'duration': 3.125}, {'end': 2257.285, 'text': "Next, when you try to compute this guy, you actually don't require this guy.", 'start': 2253.343, 'duration': 3.942}, {'end': 2266.091, 'text': "So instead of creating another guy, writing it here, why don't you just rewrite here because we don't need this guy whenever we are computing this.", 'start': 2257.826, 'duration': 8.265}, {'end': 2268.492, 'text': 'Whenever we are computing this, we will require this and this.', 'start': 2266.571, 'duration': 1.921}, {'end': 2270.013, 'text': 'This guy is of no use.', 'start': 2269.112, 'duration': 0.901}, {'end': 2272.714, 'text': "So instead of storing here, I'll come and store here.", 'start': 2270.473, 'duration': 2.241}, {'end': 2273.435, 'text': "That's what I'll do.", 'start': 2272.975, 'duration': 0.46}, {'end': 2278.018, 'text': 'and this is what we can actually write.', 'start': 2273.955, 'duration': 4.063}, {'end': 2279.499, 'text': 'so, going back to the code.', 'start': 2278.018, 'duration': 1.481}, {'end': 2280.92, 'text': 'yes, going back to the code.', 'start': 2279.499, 'duration': 1.421}, {'end': 2286.104, 'text': "what i'll do is i'll do a slide change and i'll say hey, listen, i'll read from m to one.", 'start': 2280.92, 'duration': 5.184}], 'summary': 'Optimizing code by reusing and overwriting unnecessary data, improving efficiency.', 'duration': 42.288, 'max_score': 2243.816, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/nVG7eTiD2bY/pics/nVG7eTiD2bY2243816.jpg'}, {'end': 2345.556, 'src': 'heatmap', 'start': 2316.083, 'weight': 0.737, 'content': [{'end': 2318.884, 'text': "okay, so that's the first change that i'll do.", 'start': 2316.083, 'duration': 2.801}, {'end': 2325.046, 'text': "next i'll just write previous and i'll take it off.", 'start': 2318.884, 'duration': 6.162}, {'end': 2328.368, 'text': 'right, this is done and this would have been previous j.', 'start': 2325.046, 'duration': 3.322}, {'end': 2339.734, 'text': "i need to write else, no, omit, that's the one liner that i will straight away write.", 'start': 2330.37, 'duration': 9.364}, {'end': 2345.556, 'text': "there is no other change and i'll just remove this curve perfect again.", 'start': 2339.734, 'duration': 5.822}], 'summary': "Transcript: making changes, writing 'previous' and 'else', and removing 'curve' for improvement.", 'duration': 29.473, 'max_score': 2316.083, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/nVG7eTiD2bY/pics/nVG7eTiD2bY2316083.jpg'}], 'start': 1892.116, 'title': 'Storing previous rows and code optimization', 'summary': "Outlines a process of storing previous rows' values for computation and discusses optimizing code for loop optimization, demonstrating successful execution and code performance improvement with quantifiable data.", 'chapters': [{'end': 1983.166, 'start': 1892.116, 'title': 'Storing previous rows and computing values', 'summary': "Outlines a process of storing previous rows' values for computation, using a specific example with quantifiable data and explaining the result of the computation, ultimately demonstrating the successful execution of the process.", 'duration': 91.05, 'highlights': ["The process involves storing the previous rows' value, without requiring anything else, in order to compute the current value.", "The approach entails defining a variable to store the previous rows' value and a curve which also stores the previous rows' value.", "The computation involves going through each row and placing a '1' at the 0th place for every row, dealing with two columns.", "The specific computation involves placing a '1' at the 0th place for both the previous and current values.", 'After computing the entire row, the result is returned, and the process successfully runs to completion.']}, {'end': 2405.306, 'start': 1983.166, 'title': 'Code optimization for loop optimization', 'summary': 'Discusses optimizing code for loop optimization, explaining how to reduce multiple arrays into a single array and the process of rewriting and replacing values to optimize code performance.', 'duration': 422.14, 'highlights': ['The process of rewriting and replacing values to optimize code performance, by reducing multiple arrays into a single array.', 'Analyzing and discussing the process of loop optimization and the use of previous and current values to compute the final result.', "Explaining the importance of running the code from 'm' to '1' and the implications of replacing unnecessary values during the optimization process."]}], 'duration': 513.19, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/nVG7eTiD2bY/pics/nVG7eTiD2bY1892116.jpg', 'highlights': ["The process involves storing the previous rows' value for computation", 'The process of rewriting and replacing values to optimize code performance', "The computation involves placing a '1' at the 0th place for both the previous and current values", "Explaining the importance of running the code from 'm' to '1'", "The specific computation involves placing a '1' at the 0th place for every row"]}], 'highlights': ['The code optimization resulted in improved performance, eliminating the time limit exceeded issue and ensuring efficient string matching operations.', 'The process involves declaring an identical DP array, setting the base cases, arranging the changing parameters in reverse order, and replicating the recurrence to efficiently implement tabulation.', 'The process of counting ways involves trying different methodologies and using recursion to sum up all the ways, as explained in lecture 6 and 7 of the recursion playlist.', 'The adjustment of comparison logic to handle negative indexing is emphasized as a key modification in the algorithm.', 'The chapter guarantees that after solving three LeetCode hard problems, dynamic programming on strings will appear simpler.']}