Find longest subsequnce- cant reset the array

March 20, 2024

I have a solution:

theres a task to find a longest common subsequence

function LCS(x, y) {
  let res = [];
  let temp = [];
  for (let i = 0; i < x.length; i++) {
    let val1 = x[i];
    console.log("val 1 is " + val1);
    for (let j = i; j < y.length; j++) {
      let val2 = y[j];
      console.log("val 2 is " + val2);
      if (val1 == val2) {
        console.log("they are the same");
        temp.push(val1);
        break;
      }
    }
    if (temp.length > res.length) {
      res = [...temp]; 
    }
  }
  return res.join("");
}

and for:

console.log(LCS("abxabc", "abyabc"))

the return value is:

ababc  instead of  `abc`

I think the logic is right, but i dont know why the ‘ab’ is not resseted. How to fix this? I think i only need this minor fix and the function will be completed. I want to undestand the task, not copy-paste the solution. I tried moving

temp = []

to outer loop but it didnt work.

>Solution :

Move temp into the outer loop. So you don’t need to reset it (that was your right intention).
Fill temp in the inner loop while the chars from both the loops match.
Not obligatory – you don’t need [...temp] – just assign directly.

function LCS(x, y) {
  let res = [];
  
  for (let i = 0; i < x.length; i++) {
    let temp = [];
    for (let j = i; j < y.length; j++) {
      let val1 = x[j];
      let val2 = y[j];
      if (val1 == val2) {
        temp.push(val1);
      }else{
        break;
      }
    }
    if (temp.length > res.length) {
      res = temp;
    }
  }
  return res.join("");
}

console.log(LCS("abxabc", "abyabc"))

Btw there’s no need in the temp array, just operate on indices:

function LCS(x, y) {
  let start = 0, len = 0;
  
  for (let i = 0, j; i < x.length; i++) {
    for (j = i; j < y.length && x[j] === y[j]; j++) {}
    if (j - i > len) {
      start = i, len = j - i;
    }
  }
  return x.slice(start, start + len);
}

console.log(LCS("abxabc", "abyabc"))

It’s also much faster:

` Chrome/122
-------------------------------------------------
indices     1.00x | x10000000 248 250 255 257 257
temp array  4.35x |  x1000000 108 109 111 112 115
-------------------------------------------------
https://github.com/silentmantra/benchmark `

function LCS(x, y) {
  let res = [];

  for (let i = 0; i < x.length; i++) {
    let temp = [];
    for (let j = i; j < y.length; j++) {
      let val1 = x[j];
      let val2 = y[j];
      if (val1 == val2) {
        temp.push(val1);
      }else{
        break;
      }
    }
    if (temp.length > res.length) {
      res = temp;
    }
  }
  return res.join("");
}

function LCS2(x, y) {
  let start = 0, len = 0;
  
  for (let i = 0, j; i < x.length; i++) {
    for (j = i; j < y.length && x[j] === y[j]; j++) {}
    if (j - i > len) {
      start = i, len = j - i;
    }
  }
  return x.slice(start, start + len);
}
// @benchmark temp array
LCS("abxabc", "abyabc")
// @benchmark indices
LCS2("abxabc", "abyabc")

/*@skip*/ fetch('https://cdn.jsdelivr.net/gh/silentmantra/benchmark/loader.js').then(r => r.text().then(eval));