JavaScript: Longest common subsequence

JavaScript String: Exercise-61 with Solution

Write a JavaScript function to find the length of the longest subsequence present between two sequences.
It is important to understand that a subsequence is a sequence that appears in a similar relative order, but is not necessarily contiguous.
For example, "abc", "abg", "bdf", "aeg", "acefg", .. etc are subsequences of "abcdefg"
Test Data:
("abcda", "abcdef") -> 4
("ABCD", "ACBAD") -> 3
("pqr", "pqr") -> 3
("pqr", "abc") -> 0

Sample Solution:

JavaScript Code:

 // Define a function named 'longest_Common_Subsequence' with two parameters 'text1' and 'text2'
function longest_Common_Subsequence(text1, text2) {
  // Create a 2D array 'result' with dimensions (text1.length + 1) x (text2.length + 1) filled with null values
  const result = new Array(text1.length + 1).fill(null)
    .map(() => new Array(text2.length + 1).fill(null))
  
  // Define a recursive inner function 'test' with parameters 'end1' and 'end2'
  function test(end1, end2) {
    // Base case: if either 'end1' or 'end2' reaches -1, return 0
    if (end1 === -1 || end2 === -1) {
      return 0
    }
    // If the value at the current indices in 'result' array is not null, return that value
    if (result[end1][end2] !== null) {
      return result[end1][end2]
    }
    // If the characters at the current indices in 'text1' and 'text2' are equal
    if (text1[end1] === text2[end2]) {
      // Recursively call 'test' with decremented indices and store the result in 'result' array
      result[end1][end2] = 1 + test(end1 - 1, end2 - 1)
      return result[end1][end2]
    } else {
      // If the characters are not equal, recursively call 'test' with decremented indices
      // and store the maximum value in 'result' array
      result[end1][end2] = Math.max(
        test(end1 - 1, end2),
        test(end1, end2 - 1)
      )
      return result[end1][end2]
    }
  }
  // Start the recursive function 'test' with indices at the end of 'text1' and 'text2'
  return test(text1.length - 1, text2.length - 1)
}

// Test the 'longest_Common_Subsequence' function with different input strings and output the result
console.log(longest_Common_Subsequence("abcda", "abcdef")) // Output: 5
console.log(longest_Common_Subsequence("ABCD", "ACBAD")) // Output: 3
console.log(longest_Common_Subsequence("pqr", "pqr")) // Output: 3
console.log(longest_Common_Subsequence("pqr", "abc")) // Output: 0

Output:

4
3
3
0

Explanation:

In the exercise above,

• The function creates a 2D array called 'result' initialized with null values, where result[i][j] will store the length of the longest common subsequence between the substrings text1[0...i] and text2[0...j].
• It defines an inner recursive function named "test()" that computes the length of the longest common subsequence. This function takes two indices 'end1' and 'end2' representing the end positions in the two strings being compared.
• The base case of the recursive function is when either 'end1' or 'end2' reaches -1, in which case it returns 0.
• If the value at the current indices in the 'result' array is not null, it returns that value, as it has been computed before.
• If the characters at the current indices in 'text1' and 'text2' are equal, it recursively calls "test()" with decremented indices and adds 1 to the result.
• If the characters are not equal, it recursively calls "test()" with decremented indices and stores the maximum value in the 'result' array.
• Finally, it starts the recursive function "test()" with indices at the end of 'text1' and 'text2', and returns the computed length of the longest common subsequence.

Flowchart:

Live Demo:

See the Pen javascript-string-exercise-61 by w3resource (@w3resource) on CodePen.

Improve this sample solution and post your code through Disqus.

Previous: Reverse words in a given string.
Next: Longest Valid Parentheses.