educative.io

Longest common subsequence vs substring

Courses
,
#1

Before even getting to the DP versions of the solution, when I see the recursive solutions, the main difference are in the following 2 lines:

LC Substring:
if(s1.charAt(i1) == s2.charAt(i2))
count = findLCSLengthRecursive(s1, s2, i1+1, i2+1, count+1);

LC Subsequence:
if(s1.charAt(i1) == s2.charAt(i2))
return 1 + findLCSLengthRecursive(s1, s2, i1+1, i2+1);

Of course for substring, we return the cummulative count when we reach the leaf. The subsequence returns the count (+1) as we go up the tree.

I can understand the subsequence algorithm. I am not able to understand how the substring algorithm above makes sure that we are getting a continuous “sub-string” of characters. Can someone please help with explaining that in simple terms? And I would request the author of this course to consider adding a line or 2 about this confusion in the algorithm description if you think it makes sense.

Additional question: How does adding a “1+” before calling the LCS function vs doing a “count+1” and passing it as a parameter into the function make all the difference?

thanks
-V

1 Like
#2

Soon after I asked the above question, I think I may have answered it myself. So here is what I understood -
Since we are recursing down a tree in the recursive solution, in the LC-Subsequence algorithm, we increase the count in the caller since the aggregation of the counts can happen in levels down the tree that do not necessarily need to be the immediate child - in other words, we can skip levels till we find the next match and the count is an aggregation of these levels where we found a match.
But in the case of the LC-Substring algorithm, we pass in the count to the next level since we want to increase the count if and only if we have a match at the immediate next level.
I think it is quite obvious from the function calls. But I didn’t get it the first time around. Hope this helps for someone with the same question as mine.

4 Likes
#3

@Venk good observation. I had the same confusion and your explanation made it clear.

#4

I have issue when making recursive solution is the code it’s look simple but I keep asking my self does the brute force solution works for all cases. For example, “try all substrings of ‘s1’ and ‘s2’ to find the longest common one” with that statement and the algorithm provided by the course is trying all substrings I have to draw the recursion tree to see how it done. But when building recursive solution from scratch its really hard to approach because I’ve to keep in mind that my solution must follow function stack mechanism, How do you develop an intuition for knowing what the params for the recursive helper function should be?

#5

Passing the counter down itself doesn’t give you the difference.
The difference comes from the fact that you set the counter to zero for c1,c2.
if you didn’t set it to zero you would just get LCSubsequence.

  private int findLCSLengthRecursive(String s1, String s2, int i1, int i2, int count) {
    if(i1 == s1.length() || i2 == s2.length())
      return count;

    int c0 = count;
    if(s1.charAt(i1) == s2.charAt(i2))
      c0 = findLCSLengthRecursive(s1, s2, i1+1, i2+1, count+1);

    //this gives you LCSubstring.
    int c1 = findLCSLengthRecursive(s1, s2, i1, i2+1, 0);
    int c2 = findLCSLengthRecursive(s1, s2, i1+1, i2, 0);

    /* this gives you LCSubsequence. 
    int c1 = findLCSLengthRecursive(s1, s2, i1, i2+1, count);
    int c2 = findLCSLengthRecursive(s1, s2, i1+1, i2, count);
    */
    return Math.max(c0, Math.max(c1, c2));
  }
1 Like