1
var shortestCommonSupersequence = function (str1, str2) {
2
  const lcs = getLCS(str1, str2);
3

4
  let i = 0;
5
  let j = 0;
6

7
  let result = "";
8
  for (const c of lcs) {
9
    while (i < str1.length && str1[i] !== c) {
10
      result += str1[i];
11
      i++;
12
    }
13
    while (j < str2.length && str2[j] !== c) {
14
      result += str2[j];
15
      j++;
16
    }
17
    result += c;
18
    i++;
19
    j++;
20
  }
21
  while (i < str1.length) {
22
    result += str1[i];
23
    i++;
24
  }
25
  while (j < str2.length) {
26
    result += str2[j];
27
    j++;
28
  }
29
  return result;
30
};
31

32
function getLCS(a, b) {
33
  const t = new Array(a.length + 1)
34
    .fill(0)
35
    .map(() => new Array(b.length + 1).fill(0));
36

37
  for (let i = 1; i <= a.length; i++) {
38
    for (let j = 1; j <= b.length; j++) {
39
      if (a[i - 1] === b[j - 1]) {
40
        t[i][j] = 1 + t[i - 1][j - 1];
41
      } else {
42
        t[i][j] = Math.max(t[i - 1][j], t[i][j - 1]);
43
      }
44
    }
45
  }
46

47
  let i = a.length;
48
  let j = b.length;
49
  let result = "";
50
  while (i > 0 && j > 0) {
51
    if (a[i - 1] === b[j - 1]) {
52
      result += a[i - 1];
53
      i--;
54
      j--;
55
    } else {
56
      if (t[i - 1][j] > t[i][j - 1]) {
57
        i--;
58
      } else {
59
        j--;
60
      }
61
    }
62
  }
63
  return result.split("").reverse().join("");
64
}