Find longest common string subsequence
Clash Royale CLAN TAG#URR8PPP
The task (also found at https://www.youtube.com/watch?v=10WnvBk9sZc):
Write a function that takes two strings, s1 and s2, and returns the longest common subsequence of s1 and s2.
 “ABAZDC”, “BACBAD” → “ABAD”
 “AGGTAB”, “GXTXAYB” → “GTAB”
The longest common subsequence is defined such as all of them appear in the same sequence in both strings, possiblywith other characters in between.
This is the solution I managed to come up with. I utilise the fact that once a full subsequence as been found, any subsequences that start within the boundaries of that subsequence will always be smaller in length, so I skip ahead.
const findFirstSequence = (s1, s2) => {
let subsequence = ""
let s1Idx = 0
let s2Idx = 0
for (; s1Idx < s1.length; ++s1Idx) {
const s1Char = s1[s1Idx]
for (let j = s2Idx; j < s2.length; ++j, ++s2Idx) {
const s2Char = s2[j]
if (s1Char === s2Char) {
subsequence += s1Char
++s2Idx
break
}
}
}
return subsequence
}
const removeDistinctChars = (s1, s2) => s1.split("").filter(c => s2.includes(c)).join("")
const removeDuplicates = (arr) => Array.from(new Set(arr))
const findAllSubsequences = (s1, s2) => {
const s1NoDistinct = removeDistinctChars(s1, s2)
const s2NoDistinct = removeDistinctChars(s2, s1)
let i = 0
const sequences =
while (i < s1NoDistinct.length) {
const sequence = findFirstSequence(s1NoDistinct.slice(i), s2NoDistinct)
i += sequence.length
sequences.push(sequence)
}
return sequences
}
const findLongestSubsequence = (s1, s2) => {
const a = findAllSubsequences(s1, s2)
const b = findAllSubsequences(s2, s1)
console.log('candidates:', [...a, ...b])
return removeDuplicates([...a, ...b].sort((s1, s2) => s2.length  s1.length).filter((el, idx, arr) => el.length ===
arr[0].length))
}
const test = (s1, s2) => console.log(findLongestSubsequence(s1, s2))
test("ABAZDC", "BACBAD")
test("AGGTAB", "GXTXAYB")
test("ALSKJDHJASLDH", "HNGFLKSHRADSKLASDJ")
test("aaaa", "aa")
add a comment 
The task (also found at https://www.youtube.com/watch?v=10WnvBk9sZc):
Write a function that takes two strings, s1 and s2, and returns the longest common subsequence of s1 and s2.
 “ABAZDC”, “BACBAD” → “ABAD”
 “AGGTAB”, “GXTXAYB” → “GTAB”
The longest common subsequence is defined such as all of them appear in the same sequence in both strings, possiblywith other characters in between.
This is the solution I managed to come up with. I utilise the fact that once a full subsequence as been found, any subsequences that start within the boundaries of that subsequence will always be smaller in length, so I skip ahead.
const findFirstSequence = (s1, s2) => {
let subsequence = ""
let s1Idx = 0
let s2Idx = 0
for (; s1Idx < s1.length; ++s1Idx) {
const s1Char = s1[s1Idx]
for (let j = s2Idx; j < s2.length; ++j, ++s2Idx) {
const s2Char = s2[j]
if (s1Char === s2Char) {
subsequence += s1Char
++s2Idx
break
}
}
}
return subsequence
}
const removeDistinctChars = (s1, s2) => s1.split("").filter(c => s2.includes(c)).join("")
const removeDuplicates = (arr) => Array.from(new Set(arr))
const findAllSubsequences = (s1, s2) => {
const s1NoDistinct = removeDistinctChars(s1, s2)
const s2NoDistinct = removeDistinctChars(s2, s1)
let i = 0
const sequences =
while (i < s1NoDistinct.length) {
const sequence = findFirstSequence(s1NoDistinct.slice(i), s2NoDistinct)
i += sequence.length
sequences.push(sequence)
}
return sequences
}
const findLongestSubsequence = (s1, s2) => {
const a = findAllSubsequences(s1, s2)
const b = findAllSubsequences(s2, s1)
console.log('candidates:', [...a, ...b])
return removeDuplicates([...a, ...b].sort((s1, s2) => s2.length  s1.length).filter((el, idx, arr) => el.length ===
arr[0].length))
}
const test = (s1, s2) => console.log(findLongestSubsequence(s1, s2))
test("ABAZDC", "BACBAD")
test("AGGTAB", "GXTXAYB")
test("ALSKJDHJASLDH", "HNGFLKSHRADSKLASDJ")
test("aaaa", "aa")
add a comment 
The task (also found at https://www.youtube.com/watch?v=10WnvBk9sZc):
Write a function that takes two strings, s1 and s2, and returns the longest common subsequence of s1 and s2.
 “ABAZDC”, “BACBAD” → “ABAD”
 “AGGTAB”, “GXTXAYB” → “GTAB”
The longest common subsequence is defined such as all of them appear in the same sequence in both strings, possiblywith other characters in between.
This is the solution I managed to come up with. I utilise the fact that once a full subsequence as been found, any subsequences that start within the boundaries of that subsequence will always be smaller in length, so I skip ahead.
const findFirstSequence = (s1, s2) => {
let subsequence = ""
let s1Idx = 0
let s2Idx = 0
for (; s1Idx < s1.length; ++s1Idx) {
const s1Char = s1[s1Idx]
for (let j = s2Idx; j < s2.length; ++j, ++s2Idx) {
const s2Char = s2[j]
if (s1Char === s2Char) {
subsequence += s1Char
++s2Idx
break
}
}
}
return subsequence
}
const removeDistinctChars = (s1, s2) => s1.split("").filter(c => s2.includes(c)).join("")
const removeDuplicates = (arr) => Array.from(new Set(arr))
const findAllSubsequences = (s1, s2) => {
const s1NoDistinct = removeDistinctChars(s1, s2)
const s2NoDistinct = removeDistinctChars(s2, s1)
let i = 0
const sequences =
while (i < s1NoDistinct.length) {
const sequence = findFirstSequence(s1NoDistinct.slice(i), s2NoDistinct)
i += sequence.length
sequences.push(sequence)
}
return sequences
}
const findLongestSubsequence = (s1, s2) => {
const a = findAllSubsequences(s1, s2)
const b = findAllSubsequences(s2, s1)
console.log('candidates:', [...a, ...b])
return removeDuplicates([...a, ...b].sort((s1, s2) => s2.length  s1.length).filter((el, idx, arr) => el.length ===
arr[0].length))
}
const test = (s1, s2) => console.log(findLongestSubsequence(s1, s2))
test("ABAZDC", "BACBAD")
test("AGGTAB", "GXTXAYB")
test("ALSKJDHJASLDH", "HNGFLKSHRADSKLASDJ")
test("aaaa", "aa")
The task (also found at https://www.youtube.com/watch?v=10WnvBk9sZc):
Write a function that takes two strings, s1 and s2, and returns the longest common subsequence of s1 and s2.
 “ABAZDC”, “BACBAD” → “ABAD”
 “AGGTAB”, “GXTXAYB” → “GTAB”
The longest common subsequence is defined such as all of them appear in the same sequence in both strings, possiblywith other characters in between.
This is the solution I managed to come up with. I utilise the fact that once a full subsequence as been found, any subsequences that start within the boundaries of that subsequence will always be smaller in length, so I skip ahead.
const findFirstSequence = (s1, s2) => {
let subsequence = ""
let s1Idx = 0
let s2Idx = 0
for (; s1Idx < s1.length; ++s1Idx) {
const s1Char = s1[s1Idx]
for (let j = s2Idx; j < s2.length; ++j, ++s2Idx) {
const s2Char = s2[j]
if (s1Char === s2Char) {
subsequence += s1Char
++s2Idx
break
}
}
}
return subsequence
}
const removeDistinctChars = (s1, s2) => s1.split("").filter(c => s2.includes(c)).join("")
const removeDuplicates = (arr) => Array.from(new Set(arr))
const findAllSubsequences = (s1, s2) => {
const s1NoDistinct = removeDistinctChars(s1, s2)
const s2NoDistinct = removeDistinctChars(s2, s1)
let i = 0
const sequences =
while (i < s1NoDistinct.length) {
const sequence = findFirstSequence(s1NoDistinct.slice(i), s2NoDistinct)
i += sequence.length
sequences.push(sequence)
}
return sequences
}
const findLongestSubsequence = (s1, s2) => {
const a = findAllSubsequences(s1, s2)
const b = findAllSubsequences(s2, s1)
console.log('candidates:', [...a, ...b])
return removeDuplicates([...a, ...b].sort((s1, s2) => s2.length  s1.length).filter((el, idx, arr) => el.length ===
arr[0].length))
}
const test = (s1, s2) => console.log(findLongestSubsequence(s1, s2))
test("ABAZDC", "BACBAD")
test("AGGTAB", "GXTXAYB")
test("ALSKJDHJASLDH", "HNGFLKSHRADSKLASDJ")
test("aaaa", "aa")
const findFirstSequence = (s1, s2) => {
let subsequence = ""
let s1Idx = 0
let s2Idx = 0
for (; s1Idx < s1.length; ++s1Idx) {
const s1Char = s1[s1Idx]
for (let j = s2Idx; j < s2.length; ++j, ++s2Idx) {
const s2Char = s2[j]
if (s1Char === s2Char) {
subsequence += s1Char
++s2Idx
break
}
}
}
return subsequence
}
const removeDistinctChars = (s1, s2) => s1.split("").filter(c => s2.includes(c)).join("")
const removeDuplicates = (arr) => Array.from(new Set(arr))
const findAllSubsequences = (s1, s2) => {
const s1NoDistinct = removeDistinctChars(s1, s2)
const s2NoDistinct = removeDistinctChars(s2, s1)
let i = 0
const sequences =
while (i < s1NoDistinct.length) {
const sequence = findFirstSequence(s1NoDistinct.slice(i), s2NoDistinct)
i += sequence.length
sequences.push(sequence)
}
return sequences
}
const findLongestSubsequence = (s1, s2) => {
const a = findAllSubsequences(s1, s2)
const b = findAllSubsequences(s2, s1)
console.log('candidates:', [...a, ...b])
return removeDuplicates([...a, ...b].sort((s1, s2) => s2.length  s1.length).filter((el, idx, arr) => el.length ===
arr[0].length))
}
const test = (s1, s2) => console.log(findLongestSubsequence(s1, s2))
test("ABAZDC", "BACBAD")
test("AGGTAB", "GXTXAYB")
test("ALSKJDHJASLDH", "HNGFLKSHRADSKLASDJ")
test("aaaa", "aa")
const findFirstSequence = (s1, s2) => {
let subsequence = ""
let s1Idx = 0
let s2Idx = 0
for (; s1Idx < s1.length; ++s1Idx) {
const s1Char = s1[s1Idx]
for (let j = s2Idx; j < s2.length; ++j, ++s2Idx) {
const s2Char = s2[j]
if (s1Char === s2Char) {
subsequence += s1Char
++s2Idx
break
}
}
}
return subsequence
}
const removeDistinctChars = (s1, s2) => s1.split("").filter(c => s2.includes(c)).join("")
const removeDuplicates = (arr) => Array.from(new Set(arr))
const findAllSubsequences = (s1, s2) => {
const s1NoDistinct = removeDistinctChars(s1, s2)
const s2NoDistinct = removeDistinctChars(s2, s1)
let i = 0
const sequences =
while (i < s1NoDistinct.length) {
const sequence = findFirstSequence(s1NoDistinct.slice(i), s2NoDistinct)
i += sequence.length
sequences.push(sequence)
}
return sequences
}
const findLongestSubsequence = (s1, s2) => {
const a = findAllSubsequences(s1, s2)
const b = findAllSubsequences(s2, s1)
console.log('candidates:', [...a, ...b])
return removeDuplicates([...a, ...b].sort((s1, s2) => s2.length  s1.length).filter((el, idx, arr) => el.length ===
arr[0].length))
}
const test = (s1, s2) => console.log(findLongestSubsequence(s1, s2))
test("ABAZDC", "BACBAD")
test("AGGTAB", "GXTXAYB")
test("ALSKJDHJASLDH", "HNGFLKSHRADSKLASDJ")
test("aaaa", "aa")
add a comment 
add a comment 
1 Answer
1
active
oldest
votes
Find the current max
There are some very simple improvements you can make to reduce the run time and the complexity.
Your code looks for sequences, puts them all in an array and then sorts and filters that array to find the longest. However if you check the length of each sequence as you find it and compare it against the longest you have found to that point you no longer need to keep an array of sequences, only the current longest.
This also helps reduce the amount of processing. When you know the length of the current longest sequence, you are able to know before calling findFirstSequence(s1,s2)
if it will find a longer one. The function can not find a sequence longer than the shortest string you pass it so if either is shorter than the current max then skip the call.
Also in the function findFirstSequence(s1,s2)
as you build the sequence you can workout how long it can possibly get well before you get the sequence. You can thus exit early from that function as well just by knowing the current longest sequence.
There are also two more places that you can exit early. When you first enter the function ‘findLongestSubsequence` you can check if the string are the same. If they are ether one is thus the answer.
The same after the calls to removeDistinctChars(s1, s2)
if s1NoDistinct === s2NoDistinct
then you have the answer and can return the result then.
Some style points

Use semiColons, Javascript requires them, and if you dont add them it inserts them automatically. Unfortunately it does not always put them where you may think it will. If you can not list all the times ASI (Automatic Semicolon Insertion) can ignore the line end than you are best to put them in manually.

Watch your indentation. It’s not bad, just one line is 2 space in too far. But good code does not have style errors.

Don’t leave for loop segments empty. You have
for (; s1Idx < s1.length; ++s1Idx) {
which is poor style.for (s1Idx = 0; s1Idx < s1.length; ++s1Idx) {
lets you know at a glance what the loop is starting at, rather than having to find where you set the value. In this case I would also say usei
rather thans1Idx
but that is more a personal preference.
A rewrite
So using your approach and just finding some early exits and avoiding repeated processing the following rewrite keeps track of the current longest sequence. Returning the first longest sequence found.
const findLongest = (s1, s2) => {
const removeDistinct = (s1, s2) => s1.split("").filter(c => s2.includes(c)).join("");
const findFirstSeq = (s1, s2) => {
var seq = "", i, j = 0;
for (i = 0; i < s1.length; i++) {
const c = s1[i];
while (j++ < s2.length) {
if (seq.length + (s2.length  j  2) < max) { return "" }
if (c === s2[j  1]) {
seq += c;
break;
}
}
}
return seq
}
const findSubseq = (s1, s2) => {
if (s2.length <= max  s1.length <= max) { return maxSeq }
while (s1.length && s1.length > max) {
const seq = findFirstSeq(s1, s2);
if (seq.length > max) {
max = seq.length;
s1 = s1.slice(max);
maxSeq = seq;
} else { s1 = s1.slice(1) }
}
return maxSeq;
}
var max = 0, maxSeq;
if (s1 === s2) { return s1 }
const s1D = removeDistinct(s1, s2);
const s2D = removeDistinct(s2, s1);
if (s1D === s2D) { return s1D }
findSubseq(s1D, s2D);
return findSubseq(s2D, s1D);
}
add a comment 
Your Answer
StackExchange.ifUsing(“editor”, function () {
return StackExchange.using(“mathjaxEditing”, function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [[“\$”, “\$”]]);
});
});
}, “mathjaxediting”);
StackExchange.ifUsing(“editor”, function () {
StackExchange.using(“externalEditor”, function () {
StackExchange.using(“snippets”, function () {
StackExchange.snippets.init();
});
});
}, “codesnippets”);
StackExchange.ready(function() {
var channelOptions = {
tags: “”.split(” “),
id: “196”
};
initTagRenderer(“”.split(” “), “”.split(” “), channelOptions);
StackExchange.using(“externalEditor”, function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using(“snippets”, function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: ‘answer’,
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: “”,
imageUploader: {
brandingHtml: “Powered by u003ca class=”iconimgurwhite” href=”https://imgur.com/”u003eu003c/au003e”,
contentPolicyHtml: “User contributions licensed under u003ca href=”https://creativecommons.org/licenses/bysa/3.0/”u003ecc bysa 3.0 with attribution requiredu003c/au003e u003ca href=”https://stackoverflow.com/legal/contentpolicy”u003e(content policy)u003c/au003e”,
allowUrls: true
},
onDemand: true,
discardSelector: “.discardanswer”
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave(‘#loginlink’);
});
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin(‘.newpostlogin’, ‘https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f210940%2ffindlongestcommonstringsubsequence%23newanswer’, ‘question_page’);
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
Find the current max
There are some very simple improvements you can make to reduce the run time and the complexity.
Your code looks for sequences, puts them all in an array and then sorts and filters that array to find the longest. However if you check the length of each sequence as you find it and compare it against the longest you have found to that point you no longer need to keep an array of sequences, only the current longest.
This also helps reduce the amount of processing. When you know the length of the current longest sequence, you are able to know before calling findFirstSequence(s1,s2)
if it will find a longer one. The function can not find a sequence longer than the shortest string you pass it so if either is shorter than the current max then skip the call.
Also in the function findFirstSequence(s1,s2)
as you build the sequence you can workout how long it can possibly get well before you get the sequence. You can thus exit early from that function as well just by knowing the current longest sequence.
There are also two more places that you can exit early. When you first enter the function ‘findLongestSubsequence` you can check if the string are the same. If they are ether one is thus the answer.
The same after the calls to removeDistinctChars(s1, s2)
if s1NoDistinct === s2NoDistinct
then you have the answer and can return the result then.
Some style points

Use semiColons, Javascript requires them, and if you dont add them it inserts them automatically. Unfortunately it does not always put them where you may think it will. If you can not list all the times ASI (Automatic Semicolon Insertion) can ignore the line end than you are best to put them in manually.

Watch your indentation. It’s not bad, just one line is 2 space in too far. But good code does not have style errors.

Don’t leave for loop segments empty. You have
for (; s1Idx < s1.length; ++s1Idx) {
which is poor style.for (s1Idx = 0; s1Idx < s1.length; ++s1Idx) {
lets you know at a glance what the loop is starting at, rather than having to find where you set the value. In this case I would also say usei
rather thans1Idx
but that is more a personal preference.
A rewrite
So using your approach and just finding some early exits and avoiding repeated processing the following rewrite keeps track of the current longest sequence. Returning the first longest sequence found.
const findLongest = (s1, s2) => {
const removeDistinct = (s1, s2) => s1.split("").filter(c => s2.includes(c)).join("");
const findFirstSeq = (s1, s2) => {
var seq = "", i, j = 0;
for (i = 0; i < s1.length; i++) {
const c = s1[i];
while (j++ < s2.length) {
if (seq.length + (s2.length  j  2) < max) { return "" }
if (c === s2[j  1]) {
seq += c;
break;
}
}
}
return seq
}
const findSubseq = (s1, s2) => {
if (s2.length <= max  s1.length <= max) { return maxSeq }
while (s1.length && s1.length > max) {
const seq = findFirstSeq(s1, s2);
if (seq.length > max) {
max = seq.length;
s1 = s1.slice(max);
maxSeq = seq;
} else { s1 = s1.slice(1) }
}
return maxSeq;
}
var max = 0, maxSeq;
if (s1 === s2) { return s1 }
const s1D = removeDistinct(s1, s2);
const s2D = removeDistinct(s2, s1);
if (s1D === s2D) { return s1D }
findSubseq(s1D, s2D);
return findSubseq(s2D, s1D);
}
add a comment 
Find the current max
There are some very simple improvements you can make to reduce the run time and the complexity.
Your code looks for sequences, puts them all in an array and then sorts and filters that array to find the longest. However if you check the length of each sequence as you find it and compare it against the longest you have found to that point you no longer need to keep an array of sequences, only the current longest.
This also helps reduce the amount of processing. When you know the length of the current longest sequence, you are able to know before calling findFirstSequence(s1,s2)
if it will find a longer one. The function can not find a sequence longer than the shortest string you pass it so if either is shorter than the current max then skip the call.
Also in the function findFirstSequence(s1,s2)
as you build the sequence you can workout how long it can possibly get well before you get the sequence. You can thus exit early from that function as well just by knowing the current longest sequence.
There are also two more places that you can exit early. When you first enter the function ‘findLongestSubsequence` you can check if the string are the same. If they are ether one is thus the answer.
The same after the calls to removeDistinctChars(s1, s2)
if s1NoDistinct === s2NoDistinct
then you have the answer and can return the result then.
Some style points

Use semiColons, Javascript requires them, and if you dont add them it inserts them automatically. Unfortunately it does not always put them where you may think it will. If you can not list all the times ASI (Automatic Semicolon Insertion) can ignore the line end than you are best to put them in manually.

Watch your indentation. It’s not bad, just one line is 2 space in too far. But good code does not have style errors.

Don’t leave for loop segments empty. You have
for (; s1Idx < s1.length; ++s1Idx) {
which is poor style.for (s1Idx = 0; s1Idx < s1.length; ++s1Idx) {
lets you know at a glance what the loop is starting at, rather than having to find where you set the value. In this case I would also say usei
rather thans1Idx
but that is more a personal preference.
A rewrite
So using your approach and just finding some early exits and avoiding repeated processing the following rewrite keeps track of the current longest sequence. Returning the first longest sequence found.
const findLongest = (s1, s2) => {
const removeDistinct = (s1, s2) => s1.split("").filter(c => s2.includes(c)).join("");
const findFirstSeq = (s1, s2) => {
var seq = "", i, j = 0;
for (i = 0; i < s1.length; i++) {
const c = s1[i];
while (j++ < s2.length) {
if (seq.length + (s2.length  j  2) < max) { return "" }
if (c === s2[j  1]) {
seq += c;
break;
}
}
}
return seq
}
const findSubseq = (s1, s2) => {
if (s2.length <= max  s1.length <= max) { return maxSeq }
while (s1.length && s1.length > max) {
const seq = findFirstSeq(s1, s2);
if (seq.length > max) {
max = seq.length;
s1 = s1.slice(max);
maxSeq = seq;
} else { s1 = s1.slice(1) }
}
return maxSeq;
}
var max = 0, maxSeq;
if (s1 === s2) { return s1 }
const s1D = removeDistinct(s1, s2);
const s2D = removeDistinct(s2, s1);
if (s1D === s2D) { return s1D }
findSubseq(s1D, s2D);
return findSubseq(s2D, s1D);
}
add a comment 
Find the current max
There are some very simple improvements you can make to reduce the run time and the complexity.
Your code looks for sequences, puts them all in an array and then sorts and filters that array to find the longest. However if you check the length of each sequence as you find it and compare it against the longest you have found to that point you no longer need to keep an array of sequences, only the current longest.
This also helps reduce the amount of processing. When you know the length of the current longest sequence, you are able to know before calling findFirstSequence(s1,s2)
if it will find a longer one. The function can not find a sequence longer than the shortest string you pass it so if either is shorter than the current max then skip the call.
Also in the function findFirstSequence(s1,s2)
as you build the sequence you can workout how long it can possibly get well before you get the sequence. You can thus exit early from that function as well just by knowing the current longest sequence.
There are also two more places that you can exit early. When you first enter the function ‘findLongestSubsequence` you can check if the string are the same. If they are ether one is thus the answer.
The same after the calls to removeDistinctChars(s1, s2)
if s1NoDistinct === s2NoDistinct
then you have the answer and can return the result then.
Some style points

Use semiColons, Javascript requires them, and if you dont add them it inserts them automatically. Unfortunately it does not always put them where you may think it will. If you can not list all the times ASI (Automatic Semicolon Insertion) can ignore the line end than you are best to put them in manually.

Watch your indentation. It’s not bad, just one line is 2 space in too far. But good code does not have style errors.

Don’t leave for loop segments empty. You have
for (; s1Idx < s1.length; ++s1Idx) {
which is poor style.for (s1Idx = 0; s1Idx < s1.length; ++s1Idx) {
lets you know at a glance what the loop is starting at, rather than having to find where you set the value. In this case I would also say usei
rather thans1Idx
but that is more a personal preference.
A rewrite
So using your approach and just finding some early exits and avoiding repeated processing the following rewrite keeps track of the current longest sequence. Returning the first longest sequence found.
const findLongest = (s1, s2) => {
const removeDistinct = (s1, s2) => s1.split("").filter(c => s2.includes(c)).join("");
const findFirstSeq = (s1, s2) => {
var seq = "", i, j = 0;
for (i = 0; i < s1.length; i++) {
const c = s1[i];
while (j++ < s2.length) {
if (seq.length + (s2.length  j  2) < max) { return "" }
if (c === s2[j  1]) {
seq += c;
break;
}
}
}
return seq
}
const findSubseq = (s1, s2) => {
if (s2.length <= max  s1.length <= max) { return maxSeq }
while (s1.length && s1.length > max) {
const seq = findFirstSeq(s1, s2);
if (seq.length > max) {
max = seq.length;
s1 = s1.slice(max);
maxSeq = seq;
} else { s1 = s1.slice(1) }
}
return maxSeq;
}
var max = 0, maxSeq;
if (s1 === s2) { return s1 }
const s1D = removeDistinct(s1, s2);
const s2D = removeDistinct(s2, s1);
if (s1D === s2D) { return s1D }
findSubseq(s1D, s2D);
return findSubseq(s2D, s1D);
}
Find the current max
There are some very simple improvements you can make to reduce the run time and the complexity.
Your code looks for sequences, puts them all in an array and then sorts and filters that array to find the longest. However if you check the length of each sequence as you find it and compare it against the longest you have found to that point you no longer need to keep an array of sequences, only the current longest.
This also helps reduce the amount of processing. When you know the length of the current longest sequence, you are able to know before calling findFirstSequence(s1,s2)
if it will find a longer one. The function can not find a sequence longer than the shortest string you pass it so if either is shorter than the current max then skip the call.
Also in the function findFirstSequence(s1,s2)
as you build the sequence you can workout how long it can possibly get well before you get the sequence. You can thus exit early from that function as well just by knowing the current longest sequence.
There are also two more places that you can exit early. When you first enter the function ‘findLongestSubsequence` you can check if the string are the same. If they are ether one is thus the answer.
The same after the calls to removeDistinctChars(s1, s2)
if s1NoDistinct === s2NoDistinct
then you have the answer and can return the result then.
Some style points

Use semiColons, Javascript requires them, and if you dont add them it inserts them automatically. Unfortunately it does not always put them where you may think it will. If you can not list all the times ASI (Automatic Semicolon Insertion) can ignore the line end than you are best to put them in manually.

Watch your indentation. It’s not bad, just one line is 2 space in too far. But good code does not have style errors.

Don’t leave for loop segments empty. You have
for (; s1Idx < s1.length; ++s1Idx) {
which is poor style.for (s1Idx = 0; s1Idx < s1.length; ++s1Idx) {
lets you know at a glance what the loop is starting at, rather than having to find where you set the value. In this case I would also say usei
rather thans1Idx
but that is more a personal preference.
A rewrite
So using your approach and just finding some early exits and avoiding repeated processing the following rewrite keeps track of the current longest sequence. Returning the first longest sequence found.
const findLongest = (s1, s2) => {
const removeDistinct = (s1, s2) => s1.split("").filter(c => s2.includes(c)).join("");
const findFirstSeq = (s1, s2) => {
var seq = "", i, j = 0;
for (i = 0; i < s1.length; i++) {
const c = s1[i];
while (j++ < s2.length) {
if (seq.length + (s2.length  j  2) < max) { return "" }
if (c === s2[j  1]) {
seq += c;
break;
}
}
}
return seq
}
const findSubseq = (s1, s2) => {
if (s2.length <= max  s1.length <= max) { return maxSeq }
while (s1.length && s1.length > max) {
const seq = findFirstSeq(s1, s2);
if (seq.length > max) {
max = seq.length;
s1 = s1.slice(max);
maxSeq = seq;
} else { s1 = s1.slice(1) }
}
return maxSeq;
}
var max = 0, maxSeq;
if (s1 === s2) { return s1 }
const s1D = removeDistinct(s1, s2);
const s2D = removeDistinct(s2, s1);
if (s1D === s2D) { return s1D }
findSubseq(s1D, s2D);
return findSubseq(s2D, s1D);
}
add a comment 
add a comment 
Thanks for contributing an answer to Code Review Stack Exchange!
 Please be sure to answer the question. Provide details and share your research!
But avoid …
 Asking for help, clarification, or responding to other answers.
 Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave(‘#loginlink’);
});
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin(‘.newpostlogin’, ‘https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f210940%2ffindlongestcommonstringsubsequence%23newanswer’, ‘question_page’);
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave(‘#loginlink’);
});
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave(‘#loginlink’);
});
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave(‘#loginlink’);
});
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown