Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
longest subsequence between two strings
/*
Given two strings s1 and s2, return the longest common subsequence of s1 and s2
(with longest common subsequence defined as the longest sequence of characters
such that all of them appear in both of the strings, possibly with other characters in between)
'ABAZDC' 'BACBAD' => ABAD
'AGGTAB' 'GXTXAYB' => GTAB
'aaaa' 'aa' => aa
*/
console.log(getLongestSub('ABAZDC','BACBAD'));
console.log(getLongestSub('AGGTAB','GXTXAYB'));
console.log(getLongestSub('aaaa','aa'));
function getLongestSub(str1, str2, memo = []) {
if (!str1.length || !str2.length) return '';
let first, second;
if ( str1.length >= str2.length )
{
first = str1;
second = str2;
} else {
first = str2;
second = str1;
}
const letter = first.charAt(0);
const idx = second.indexOf(letter);
if( idx >= 0 ) {
memo.push(letter);
getLongestSub(first.substring(1), second.substring(idx + 1), memo);
} else {
getLongestSub(first.substring(1), second, memo);
}
return memo.join('');
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment