Longest Word in Dictionary through Deleting
Medium · Two Pointers · Array · Two Pointers · String · Sorting
Problem
You are given a string s and a list of words dictionary. Find the longest word in dictionary that can be made by deleting some characters of s without reordering the rest; in other words, the word is a subsequence of s.
If several words of that length qualify, return the one that comes first in alphabetical order. If no word qualifies, return the empty string "".
Examples
Input: s = "bxaypplez", dictionary = ["apple","bay","zebra","bapple"] Output: "bapple"
"bapple" can be read inside s in order (b, a, p, p, l, e) and is the longest word that can. "zebra" cannot: there is no b after the z.
Input: s = "cabd", dictionary = ["cd","ab","xyz"] Output: "ab"
"cd" and "ab" both fit and both have length 2; "ab" comes first alphabetically.
Input: s = "qq", dictionary = ["a"] Output: ""
No word fits, so the answer is the empty string.
Constraints
- 1 <= len(s) <= 1000
- 1 <= len(dictionary) <= 1000
- 1 <= len(dictionary[i]) <= 1000
- s and every word consist of lowercase English letters.
Approaches
- Longest common subsequence check per word — time O(D · n · L), space O(L)
Follow-up
With many words and a long s, precompute nxt[i][c]: the first position at or after i where letter c occurs. Each word is then checked in O(its length) by jumping, independent of len(s), for O(26 · n + total word length) overall.
Related problems
Start free on Cariara · Coding problems · System design studio
