Longest Word in Dictionary through Deleting

Longest Word in Dictionary through Deleting

What is this problem about?

In this string problem, you are given a string s and an array of dictionary words. You need to find the longest word in the dictionary that can be formed by deleting some (or zero) characters from the string s. If multiple valid words have the same maximum length, you must return the lexicographically smallest one.

Why is this asked in interviews?

This is a classic Two Pointers and string parsing question. Interviewers use it to evaluate whether a candidate can write an efficient subsequence validation function. It tests optimization skills; checking subsequences can be computationally expensive, so candidates are pushed to organize their logic to minimize unnecessary comparisons and handle strict tie-breaking conditions cleanly.

Algorithmic pattern used

This problem relies on Two Pointers and Iterative Search. For each word in the dictionary, you use a two-pointer approach to check if it is a valid subsequence of s. One pointer tracks s, and the other tracks the dictionary word. If it is a valid subsequence, you compare its length and lexicographical value against your currently stored "best" word, updating the best word if the new one is longer, or same length but alphabetically smaller.

Example explanation

String s = "abpcplea", Dictionary = ["ale", "apple", "monkey", "plea"].

• Check "ale": Is it a subsequence of "abpcplea"? Yes. Best = "ale".
• Check "apple": Is it a subsequence? Yes. Length 5 is $> 3$. Best = "apple".
• Check "monkey": Is it a subsequence? No ('m' is missing).
• Check "plea": Is it a subsequence? Yes. Length is 4. Length 4 is not $> 5$. Ignore. The final result is "apple". If the dictionary had both "apple" and "apply", and both were subsequences, "apple" would win because it comes first alphabetically.

Common mistakes candidates make

A common error is trying to generate all possible subsequences of s and checking if they exist in the dictionary. Since a string of length $N$ has $2^N$ subsequences, this approach will immediately cause a Time Limit Exceeded error. You must iterate over the dictionary words and validate them against s, not the other way around. Another mistake is sorting the entire dictionary first; while it works, it is mathematically slower than just maintaining a running "best" string during a single linear scan.

Interview preparation tip

For the Longest Word in Dictionary through Deleting interview pattern, isolate your logic into a helper function isSubsequence(word, s). Keeping this loop clean (advancing the word pointer only when characters match, while always advancing the s pointer) proves to the interviewer that you understand separation of concerns and modular code design.