Longest Common Subsequence

Aug 15, 2023

Longest Common Subsequence

Given two strings, find longest common subsequence between them.
https://github.com/mission-peace/inte…
https://github.com/mission-peace/inte…

Content

2.139 -> Hello friends, my name is Tushar and today,

4.509 -> we're going to look at the question, Longest Common Subsequence.

7.54 -> What is this question? Given two strings,

10.71 -> how do we find the longest common subsequence between them?

13.719 -> So, for these particular two strings, "abcdaf"

17.699 -> "acbcf", the longest common subsequence

21.71 -> will be 'a', 'a', 'b', 'b'

25.26 -> 'c', 'c', 'f' and 'f'.

28.369 -> So, the length of the longest common subsequence will be four.

31.5 -> and the longest common subsequence will be 'a','b','c' and 'f' , so, the thing with subsequence

36.5 -> is that

36.579 -> it need not be continuous in the string, so, here

39.829 -> 'a', 'b', 'c' and 'f' and we ignored 'c', and above

43.54 -> 'a', 'b', 'c' and 'f' and we ignored couple of charcters in between.

47.37 -> So, how do we find the longest common Subsequence? Yes, we will use Dynamic

50.809 -> Programming to solve this question.

53.66 -> So, here I have

54.82 -> on the first row, i have the first string

58.329 -> 'a', 'b' ,'c', 'd', 'a', 'f'

61.609 -> and on the first column, i have the other string

64.67 -> 'a', 'c', 'b', 'c' and 'f', second row and second column

69.15 -> are just populated with zeros, alright, so, now let's fill this matrix.

73.97 -> and finally, we'll have our solution when the matrix is totally filled.

78.9 -> So, when i'm filling this particular point

81.2 -> in the matrix, I'm asking myself if i had a

83.85 -> string "a" and "a" and nothing else, whatever will be the longest common subsequence here

89.42 -> so, the length of the longest common subsequence here will be one

92.65 -> when i have just these two guys, so, one.

95.77 -> now, i have strings "ab" and "a".

99.4 -> So, if i have strings "ab" and "a",

102.479 -> What is the length of the longest common subsequence here? again of length one.

106.61 -> when i have strings "abc" and "a",

109.78 -> What is the length of the longest common subsequence here?

113.22 -> Again length one, one, one, and one.

116.88 -> so if we had string "abcdaf" on one side and

122 -> just "a" on the other side, the longest common subsequence there

125.57 -> will be "a". Now, we'll fill

128.709 -> for this third row.

132.79 -> which will now include 'c'.

135.61 -> So, here we'll have 'a' and 'c' on one side and "a" on other side.

140.14 -> so, you'll ask yourself if I had string "ac" and "a",

144.78 -> what is the longest common subsequence here?

147.489 -> again one. Where did we get this one from? From the top.

151.26 -> so what we're saying is, if these two guys

155.22 -> are not same, then the length of the longest common subsequence will be

159.909 -> max of either the guy at the top or

162.909 -> the guy in the left. In this case, this is one so, it becomes one.

166.29 -> We have string "ab" and "ac", What is the length of the longest common subsequence here?

171.319 -> since 'c' and 'b' are not same, the value

174.69 -> here will be either the max of this or this. So, in this case, it's again one.

179.23 -> Here, we have string

181.31 -> "abc" and "ac", now, 'c' and 'c' are same,

185.4 -> so, the length of longest common subsequence

188.439 -> will be one because 'c' and 'c' are same plus

191.84 -> whatever the best we did between "ab" and "a", so this one.

195.599 -> so, one plus one two, so, again if these two guys are same,

199.239 -> so the length of the longest common subsequence will be this

202.5 -> plus one and if they are not same, then the max of this or this.

206.919 -> Let's fill 'd' in the same way. So, since 'c' and 'd' are not same,

211.569 -> we get the value from here, so two, two and two.

216.44 -> Alright let's move here.

218.449 -> if you have strings "acb" and "a",

222.489 -> the length of the longest common subsequence will be one

226.669 -> the guy from here. For now,

228.18 -> 'b' and 'b' are same. So, the length of the longest common subsequence will be

232.28 -> this guy, diagonaly cross guy plus one, so two.

236.379 -> again 'b' and 'c' are not same,

239.599 -> so, the length will be max of these two which is two. Here, these guys are not same, so

245.799 -> max of these two, which is two, two and two.

249.47 -> Alright, let's move to next row.

252.949 -> So, here, we've

255.88 -> 'c' and 'a', and they're not same, so the value from the top

260.17 -> one. Here, 'c' and 'b' are not same

263.27 -> so value from, max of this or this, so, two.

267.31 -> 'c' and 'c' are same, so,

270.27 -> we go diagonally across, so, two

273.5 -> plus one, three. Again, when these two guys are same,

277 -> we are saying is that we already know that these guys will cntribute one to the

281.64 -> longest common subsequence

283.3 -> and we'll see the best we can do without these two guys. So, that is "ab" and "acb",

288.74 -> for which the number is here, two so, two plus one three.

293.42 -> This here is not same, so max of this this, so three.

297.75 -> they're not same, three they're not same, so three.

301.96 -> Let's fill up the last row.

305.83 -> So, one, two, three.

310.45 -> three, three. Since these two guys are same,

314.7 -> so, the value will be three plus one four, so, this is the lenght of our,

320.14 -> this is the length of the Longest Common Subsequence between them.

323.23 -> now if you want to find what that actual subsequence is,

327.4 -> we'll do this. So, we will start from here

330.19 -> and we'll see where this four is coming from? So, this four is not coming from

334.4 -> these two guys.

335.43 -> So, it's got to be coming from here. So, we know that 'f' is in the answer.

338.82 -> so, we'll move here.

342.66 -> Three. Where is this three coming from?

346.1 -> this three is coming from here, so, we moved

349.61 -> one step here, Where is this three coming from? This three is coming from here.

354.55 -> so we move one here. Where is this three coming from?

358.8 -> This three is coming from here, so we moved diagonal and whenever we move diagonal, we

363.7 -> include that

364.57 -> character, 'c', where is this two coming from?

370.14 -> this two is coming from here

373.6 -> So, we'll include 'b'.

379.839 -> and where is this one coming from? Top and where is this one coming from? here.

383.65 -> So, we'll include 'a'. Alright, so this is the

388.55 -> final result, 'a', 'b', 'c' and 'f' is our Longest Common Subsequence.

394.3 -> and the length is four. How would the formula look like?

399.559 -> Let me quickly write the formula.

411.449 -> if input[i]

416.69 -> equal equal to

419.43 -> if input1[i] is equal equal to input2[j],

426.36 -> then,

427.61 -> T[i][j] is equal to T[i-1][j-1] plus one,

441.69 -> else,

442.4 -> T[i][j] = max(T[i-1][j], T[i][j-1])

460.25 -> If you want the full solution for this problem,

465.74 -> Go to my Github Link: github.com/mission-peace/interview/wiki

468.9 -> Thanks for watching this video.

Source: https://www.youtube.com/watch?v=NnD96abizww