1
00:00:00,820 --> 00:00:02,860
Hey there and welcome back.

2
00:00:03,340 --> 00:00:10,690
Let's get started with the very famous coding interview question called the LCS question, or the Longest

3
00:00:10,690 --> 00:00:12,910
Common Subsequence question.

4
00:00:12,940 --> 00:00:14,050
Let's read it.

5
00:00:14,720 --> 00:00:23,780
Given two strings, text one and text two return the length of their longest common subsequence.

6
00:00:23,780 --> 00:00:27,440
If there is no common subsequence, return zero.

7
00:00:27,950 --> 00:00:34,640
A subsequence of a string is a new string generated from the original string with.

8
00:00:34,640 --> 00:00:42,860
Some characters can be none deleted without changing the relative order of the remaining characters.

9
00:00:42,860 --> 00:00:47,750
For example, a c is a subsequence of a, b, c, d, e.

10
00:00:47,840 --> 00:00:55,220
Notice over here you have a, you have C, you have e, so you have just deleted b and D, and you have

11
00:00:55,220 --> 00:01:00,980
not changed the relative order in which A, c, and e occurred in this string.

12
00:01:00,980 --> 00:01:06,170
So that's how a c is a subsequence of a, b, c, d, e.

13
00:01:06,590 --> 00:01:14,420
And then it says a common subsequence of two strings is a subsequence that is common to both strings.

14
00:01:14,420 --> 00:01:15,860
So this is the question.

15
00:01:15,860 --> 00:01:17,930
And we are given an example.

16
00:01:17,930 --> 00:01:27,110
So if the two strings given to us are a, b, c, d, e, f and a c e f, then the required output is

17
00:01:27,110 --> 00:01:27,590
four.

18
00:01:27,590 --> 00:01:28,100
Because.

19
00:01:28,100 --> 00:01:36,680
Notice over here a c, e, f is a subsequence in this string and a c e f is a subsequence over here

20
00:01:36,680 --> 00:01:37,280
as well.

21
00:01:37,280 --> 00:01:43,910
And in fact this is the longest common subsequence, and the length of this subsequence is four because

22
00:01:43,910 --> 00:01:45,380
you have four characters over here.

23
00:01:45,500 --> 00:01:47,060
So this is the question.

24
00:01:47,060 --> 00:01:51,800
And remember a subsequence is different from a substring.

25
00:01:51,800 --> 00:01:58,520
Now in a substring you would not be able to delete characters in between, but in a subsequence.

26
00:01:58,520 --> 00:02:05,150
It's okay to delete some characters in between, but you just need to maintain the relative order.

27
00:02:05,150 --> 00:02:06,650
So that's a subsequence.

28
00:02:06,650 --> 00:02:13,280
Now let's proceed and go ahead and ask any clarifying questions that you may have.

29
00:02:13,280 --> 00:02:18,710
Because remember it's always important to ask questions when you're presented with a coding interview

30
00:02:18,710 --> 00:02:23,240
question to ensure that you and the interviewer are on the same page.

31
00:02:23,240 --> 00:02:29,150
Now, a possible question that you could ask over here is will there be uppercase characters?

32
00:02:29,150 --> 00:02:32,930
And if they are there, how would you want them to be treated?

33
00:02:32,930 --> 00:02:39,680
Now let's say the interviewer replies, no, you will be only given lowercase characters in the two

34
00:02:39,680 --> 00:02:40,430
strings.

35
00:02:40,910 --> 00:02:47,150
Another question that you may want to ask the interviewer is, is it possible to be given empty strings?

36
00:02:47,150 --> 00:02:49,520
And let's say the interviewer replies, no.

37
00:02:49,520 --> 00:02:54,380
There will be minimum of one character in each of the two strings.

38
00:02:54,470 --> 00:02:57,440
All right, so we have understood the question.

39
00:02:57,440 --> 00:03:02,420
We have understood what is asked of us, and we have asked clarifying questions.

40
00:03:02,420 --> 00:03:05,960
Let's now proceed and write a few test cases.

41
00:03:05,960 --> 00:03:13,370
And always remember it's okay to come up with test cases together with your interviewer so that you

42
00:03:13,370 --> 00:03:17,540
can be sure that you are trying to address what is actually asked of you.

43
00:03:17,540 --> 00:03:24,560
Now, we've already seen the example where A, B, C, D, e, f and a, c, e, f were the two strings

44
00:03:24,560 --> 00:03:27,260
and the desired output was four.

45
00:03:27,530 --> 00:03:32,600
Another case could be let's say the two strings are a and B, and because.

46
00:03:32,600 --> 00:03:38,600
Notice that there is no common subsequence between these two, the desired output would be zero.

47
00:03:39,050 --> 00:03:46,790
If the strings that are given are a, b and a, the desired output would be one, and if you're given

48
00:03:46,790 --> 00:03:50,990
a b and a b, then the desired output would be two.

49
00:03:51,320 --> 00:03:56,060
So we have written some interesting test cases as well as we have understood the question.

50
00:03:56,060 --> 00:04:01,190
Now in the next video, let's think about what approach we can take to solve this question.