Hey there and welcome back.
Let's get started with the very famous coding interview question called the LCS question, or the Longest
Common Subsequence question.
Let's read it.
Given two strings, text one and text two return the length of their longest common subsequence.
If there is no common subsequence, return zero.
A subsequence of a string is a new string generated from the original string with.
Some characters can be none deleted without changing the relative order of the remaining characters.
For example, a c is a subsequence of a, b, c, d, e.
Notice over here you have a, you have C, you have e, so you have just deleted b and D, and you have
not changed the relative order in which A, c, and e occurred in this string.
So that's how a c is a subsequence of a, b, c, d, e.
And then it says a common subsequence of two strings is a subsequence that is common to both strings.
So this is the question.
And we are given an example.
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
four.
Because.
Notice over here a c, e, f is a subsequence in this string and a c e f is a subsequence over here
as well.
And in fact this is the longest common subsequence, and the length of this subsequence is four because
you have four characters over here.
So this is the question.
And remember a subsequence is different from a substring.
Now in a substring you would not be able to delete characters in between, but in a subsequence.
It's okay to delete some characters in between, but you just need to maintain the relative order.
So that's a subsequence.
Now let's proceed and go ahead and ask any clarifying questions that you may have.
Because remember it's always important to ask questions when you're presented with a coding interview
question to ensure that you and the interviewer are on the same page.
Now, a possible question that you could ask over here is will there be uppercase characters?
And if they are there, how would you want them to be treated?
Now let's say the interviewer replies, no, you will be only given lowercase characters in the two
strings.
Another question that you may want to ask the interviewer is, is it possible to be given empty strings?
And let's say the interviewer replies, no.
There will be minimum of one character in each of the two strings.
All right, so we have understood the question.
We have understood what is asked of us, and we have asked clarifying questions.
Let's now proceed and write a few test cases.
And always remember it's okay to come up with test cases together with your interviewer so that you
can be sure that you are trying to address what is actually asked of you.
Now, we've already seen the example where A, B, C, D, e, f and a, c, e, f were the two strings
and the desired output was four.
Another case could be let's say the two strings are a and B, and because.
Notice that there is no common subsequence between these two, the desired output would be zero.
If the strings that are given are a, b and a, the desired output would be one, and if you're given
a b and a b, then the desired output would be two.
So we have written some interesting test cases as well as we have understood the question.
Now in the next video, let's think about what approach we can take to solve this question.