RWC: Longest Word That's a Subsequence

longest-word.js

/**
 * Comparison function for sorting an array of strings by length
 * @param {string} a first word from dictionary
 * @param {string} b second word from dictionary
 * @return {number} relative order of the two strings
 */
function byLength(a, b) {
	return b.length - a.length;
}

/**
 * Determines whether the provided word is a subsequence of the provided sequence
 * @param {string} word 
 * @param {string} sequence
 * @returns {boolean} true if the letters in `word` appear in order in `sequence`
 */
function isSubsequence(word, sequence) {
	for (let letter of sequence) {
		if (word.startsWith(letter)) {
			word = word.substring(1);

			// All letters of the word have been accounted for
			if (word === '') {
				return true;
			}
		}
	}

	return false;
}

/**
 * Determines the longest word that is a subsequence of the provided string
 * @param {string} str sequence
 * @param {string[]} dict list of words to check against the sequence
 * @returns {string} longest subsequence
 */
function longestWord(str, dict) {
	const subsequences = dict.filter(word => isSubsequence(word, str));
	subsequences.sort(byLength);
	return subsequences[0];
}

console.log(
	longestWord(
		'abppplee',
		['able', 'ale', 'apple', 'bale', 'kangaroo']
	)
);