Longest Word in Dictionary through Deleting - Video Solutions

Problem Overview: Given a string s and a list of dictionary words, find the longest word that can be formed by deleting some characters from s. The resulting word must be a subsequence of s. If multiple words have the same maximum length, return the lexicographically smallest one.

Approach 1: Two-Pointer Technique (Time: O(n * m), Space: O(1))

This approach checks whether each dictionary word is a subsequence of s. Use two pointers: one for the main string and one for the candidate word. Iterate through s while advancing the second pointer whenever characters match. If the pointer for the dictionary word reaches its end, the word is a valid subsequence. Track the best result by comparing lengths first and lexicographic order second. The idea relies on efficient linear scanning rather than generating all subsequences, which would be exponential. This method is simple, memory-efficient, and works well when the dictionary size is moderate.

Since each subsequence check scans s, the complexity becomes O(D * |s|) where D is the number of dictionary words. Only a few variables are stored, so space remains O(1). This approach frequently appears in problems involving Two Pointers and String traversal.

Approach 2: Sorting and Checking (Time: O(D log D + D * |s|), Space: O(1) or O(D) depending on sort)

Another strategy sorts the dictionary first, prioritizing longer words and breaking ties using lexicographical order. After sorting, iterate through the dictionary and check each word using the same two-pointer subsequence check. The first valid word found is immediately the correct answer because the ordering guarantees maximum length and smallest lexicographic value.

Sorting costs O(D log D), and each subsequence verification still costs O(|s|). The advantage is early termination: you often stop after checking only a few words. This makes the method practical when the dictionary is large but contains many short candidates. The approach combines ideas from Array traversal and Sorting with subsequence validation.

Recommended for interviews: The two-pointer subsequence check is the core technique interviewers expect. It shows you recognize the subsequence pattern and can implement it efficiently in linear time. Sorting the dictionary first is a useful optimization that demonstrates awareness of lexicographic constraints and early stopping. A strong solution explains the two-pointer subsequence logic clearly and then discusses sorting as a practical improvement.