longest-seq-unoptimized.js

// ABAZDC, BACBAD => ABAD
// AGGTAB, GXTXAYB => GTAB
// aaaa, aa => aa

const getLongestSubseq = function(s1, s2) {
    let longest = null

    for ( let s1from=0; s1from<s1.length; ++s1from ) {
        let current = []
        let s1i = s1from, s2i = 0

        while ( s1i < s1.length && s2i < s2.length ) {
            let char1 = s1[s1i]
            let char2index = s2.indexOf(char1, s2i)

            if ( char2index > -1 ) {
                current.push(char1)
                s1i++
                s2i = char2index + 1
            } else {
                s1i++
            }
        }

        if ( !longest || current.length > longest.length ) {
            longest = current
        }
    }

    return longest ? longest.join("") : ""
}

console.assert(getLongestSubseq("ABAZDC", "BACBAD") === "ABAD")
console.assert(getLongestSubseq("AGGTAB", "GXTXAYB") === "GTAB")
console.assert(getLongestSubseq("aaaa", "aa") === "aa")