Finding out the least-change operation to re-order a JS array

Question

I have got two JavaScript arrays - original and reordered. Assume that both arrays have the same items and each item in the array is unique. The corresponding items in both arrays may or may not be in the same order.

The original items of my problem are JS objects, but for demonstration's sake, I will just use strings here. So for example:

var original = ["life", "is", "trying", "things", "to", "see", "if", "they", "work"];
var reordered = ["life", "they", "is", "trying", "to", "things", "work", "see", "if"];

So my task is to create a third array (let's call it extracts) containing the items that need to be taken out from original and reinsert back into the original in order to transform original in the order of reordered.

Using the above example, the worked-out extracts would probably be:

extracts = ["things", "they", "work"];

After extraction, original would become:

original = ["life", "is", "trying", "to", "see", "if"];

Using this extracts array, I can then reinsert each item into the original accordingly to form reordered

But the problem is: how can I programmatically work out the shortest extracts array possible for the task? In other words, how can I take out the least number of items from original to form the reordered?

---

Bonus It would be great if the items in extracts are sorted in the relative order of reordered. Using the above example, it would be:

extracts = ["they", "things", "work"];

Answer 1

Compute the dynamic programming table for a longest common subsequence and then walk it to determine the reverse order in which words were deleted from reordered.

let original = ["life", "is", "trying", "things", "to", "see", "if", "they", "work"];
let reordered = ["life", "they", "is", "trying", "to", "things", "work", "see", "if"];
let table = [[0]];
for (let j = 0; j < reordered.length; ++j) {
  table[0].push(0);
}
for (let i = 0; i < original.length; ++i) {
  table.push([0]);
  for (let j = 0; j < reordered.length; ++j) {
    table[i + 1].push(
      original[i] == reordered[j]
        ? table[i][j] + 1
        : Math.max(table[i][j + 1], table[i + 1][j])
    );
  }
}
let extracts = [];
let i = original.length - 1;
let j = reordered.length - 1;
while (i >= 0 && j >= 0) {
  if (original[i] == reordered[j]) {
    --i;
    --j;
  } else if (table[i + 1][j + 1] == table[i][j + 1]) {
    --i;
  } else {
    extracts.push(reordered[j]);
    --j;
  }
}
while (j >= 0) {
  extracts.push(reordered[j]);
  --j;
}
extracts.reverse();
console.log(extracts);