633. The Longest Word You Can Spell by Deleting

A source string is given, along with a list of candidate words. A word can be SPELLED when it can be obtained from the source by deleting some characters, without reordering what is left.

Print the longest word that can be spelled. If several are equally long, print the one that comes first alphabetically. If none can be spelled, print none.

source abpcplea, words ale apple monkey plea -> apple source bab, words ba ab -> ab both fit, ab sorts first source abc, words d -> none

## The subsequence test IS a two-pointer scan

One pointer walks the SOURCE and one walks the CANDIDATE. Advance the candidate pointer only when the characters match:

i = 0 for each character c of source: if i < len(word) and word[i] == c: i += 1 answer: i == len(word)

The source pointer advances every step regardless, so this is one pass per word.

## Why greedily matching the earliest occurrence is correct

At each step the scan matches word[i] against the FIRST place it can. That never loses an answer: if some valid matching used a later occurrence of that character, then swapping in the earlier one leaves at least as much of the source available for the rest of the word.

So no backtracking is needed, which is why this is a linear scan rather than a search.

## Why this is not problem 519

Problem 519 asks whether one string is a subsequence of another: a single yes or no. This asks which of MANY candidates is best, so the scan is the inner loop and the outer work is the comparison between winners.

## The tie-break has to be applied in the right order

Longest first, then alphabetical. Comparing alphabetically first gives the wrong answer whenever a short early word beats a long late one.

On bab with ba and ab, both spell and both have length 2, so ab wins on the second rule. On aaa with aa, aaa and aaaa, the answer is aaa: aaaa needs four characters and the source has three.

## The cost, and when it matters

Each candidate costs O(len(source)), so the total is O(w * len(source)). When there are very many candidates, a better approach precomputes, for each position and letter, the next occurrence, and then each word costs O(len(word) * log) or better.

That is not needed at these limits, and reaching for it first is a common way to overcomplicate the answer to this question.

## Boundaries

A word longer than the source can never be spelled. A word equal to the source spells exactly.

## Cost

Time O(w * len(source)). Space O(1) beyond the input.

Constraints - `1 ≤ length of the source ≤ 200000` - `1 ≤ w ≤ 1000` - `1 ≤ length of each word ≤ 1000` - all strings are lowercase letters