Skip to content

Instantly share code, notes, and snippets.

@adyngom
Last active June 13, 2019 04:23
Show Gist options
  • Save adyngom/e6f1d6d17fbcaa11b5ac1f09c279b5c2 to your computer and use it in GitHub Desktop.
Save adyngom/e6f1d6d17fbcaa11b5ac1f09c279b5c2 to your computer and use it in GitHub Desktop.
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