Return a longest common subsequence of two strings
Diff tools such as git diff start from one question: what is the longest run of content two versions share, in order, even if other content was inserted between? Implement commonSubsequence(a, b), which returns a longest string that is a subsequence of both a and b.
commonSubsequence(a, b) // => string
'fnd' is a subsequence of 'frontend'; 'dnf' is not.''.'A' and 'a' differ. Treat strings as sequences of UTF-16 code units (plain indexing, a[i]).commonSubsequence('frontend', 'friend'); // => 'frend'
commonSubsequence('banana', 'atana'); // => 'aana'
commonSubsequence('react', 'redux'); // => 're'
commonSubsequence('ab', 'ba'); // => 'a' or 'b'
commonSubsequence('Abc', 'abc'); // => 'bc'
commonSubsequence('xyz', 'abc'); // => ''
commonSubsequence('', 'abc'); // => ''
Because several answers can be correct, most tests check that your result has the expected length and is a subsequence of both inputs, rather than comparing it to one fixed string. When only one longest common subsequence exists, the test compares the exact string.