Given a string s and a string array dictionary, return the longest string in the dictionary that can be formed by deleting some of the given string characters. If there is more than one possible result, return the longest word with the smallest lexicographical order. If there is no possible result, return the empty string.
Example 1:
Input: s = "abpcplea", dictionary = ["ale","apple","monkey","plea"] Output: "apple"
Example 2:
Input: s = "abpcplea", dictionary = ["a","b","c"] Output: "a"
Constraints:
1 <= s.length <= 10001 <= dictionary.length <= 10001 <= dictionary[i].length <= 1000s and dictionary[i] consist of lowercase English letters.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.
This approach involves using a two-pointer technique to check if a string from the dictionary is a subsequence of the given string s. We iterate through each word in the dictionary and for each word, use two pointers to traverse through the word and s. If all characters of the word are found in the same order in s, then it's a valid word. We maintain a result variable to track the longest valid word found so far, and if multiple are of the same length, we track the smallest lexicographical order.
The solution defines a helper function isSubsequence that determines if a given word is a subsequence of s by using two pointers: one traversing s and the other traversing the word. The main logic iterates through each word in the dictionary and checks if it is a subsequence, updating the result if it is longer or lexicographically smaller than the previous result.
s. This is because we potentially traverse the entire string for each dictionary word.This approach involves sorting the dictionary by length (descending) and lexicographical order (ascending). By sorting first, you can ensure that you are checking the longest available words first while resolving ties based on the smallest alphabetical order. We then iterate through this sorted list and use a function to check if a word is a valid subsequence of s.
This Python implementation uses sorting to align words by the desirable evaluation order: first longest, then smallest lexicographically. The `is_subsequence` function checks if a word is a subsequence of `s`, as before accomplished using iterators for efficiency.
| Approach | Complexity |
|---|---|
| Two-Pointer Technique |
|
| Sorting and Checking |
|
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Two-Pointer Technique | O(D * |s|) | O(1) | General case. Simple subsequence check for each dictionary word without preprocessing. |
| Sorting and Checking | O(D log D + D * |s|) | O(1)–O(D) | When you want early termination by checking longest and lexicographically smallest words first. |
Longest Word in Dictionary through Deleting | Live Coding with Explanation | Leetcode - 524 • Algorithms Made Easy • 6,360 views views
Watch 9 more video solutions →Practice Longest Word in Dictionary through Deleting with our built-in code editor and test cases.
Practice on FleetCode