5
\$\begingroup\$

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")

\$\endgroup\$
4
\$\begingroup\$

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 use i rather than s1Idx 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);
}
\$\endgroup\$

protected by Simon Forsberg Jun 10 at 16:19

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.