524. Longest Word in Dictionary through Deleting
Model: qwen3.5:9b
Topics: Two Pointers,Sort
FAANG asked: 0
Acceptance rate: 50.1%
Problem Breakdown
We are given a source string s and a list of candidate words (dictionary). The goal is to find which word from the dictionary can be formed by deleting zero or more characters from s. In other words, we need to check if each dictionary word is a subsequence of s.
Among all valid subsequences found:
- We want the one with the maximum length.
- If there’s a tie in length, we pick the lexicographically smallest string (e.g., “apple” over “apply”).
- If no word from the dictionary is a subsequence of
s, return an empty string.
Constraints & Edge Cases:
- Length Limits: Both strings are up to 1000 characters, and there are up to 1000 words in the dictionary. This suggests an solution is acceptable ( = dict size, = string length).
- Empty Result: If no word matches, return
"". The initialization of our result variable should handle this naturally (e.g., start with empty string or a flag). - Tie-Breaking: Crucial to ensure we don’t overwrite the best answer just because lengths are equal; we must check lexicographical order.
Intuition
The core task is validation: for every word in dictionary, determine if it exists as a subsequence within s.
A brute-force approach would be checking each dictionary word against s one by one. Since the constraints allow and length , performing this check for all words is computationally feasible ( operations).
The key insight isn’t about reducing complexity class (like using a Trie), but rather how we track our “best” candidate. We maintain one variable, say result, initialized to an empty string. As we iterate through the dictionary:
- If the current word is valid in
s:- Is it longer than
len(result)? Yes -> Updateresult. - No, but same length? Check if
current_word < result(lexicographically). Yes -> Updateresult.
- Is it longer than
This greedy approach works because we need to scan all candidates anyway. Sorting the dictionary beforehand isn’t strictly necessary for correctness or asymptotic performance here, though it could simplify logic slightly by processing longest words first; however, standard iteration with a conditional update is cleaner and robust against edge cases like multiple valid words of varying lengths appearing in any order.
Approach
- Initialize
resultas an empty string (""). This handles the “no match” case automatically since we only overwrite if conditions are met. - Iterate through each word in
dictionary. - For each word, use a two-pointer technique to check subsequence validity:
- Pointer
ifor source strings, pointerjfor current dictionary word. - Advance both pointers if characters match; advance only
iotherwise until we find the character or reach end ofs.
- Pointer
- If valid, compare with
result:- Update if
len(word) > len(result)OR (len(word) == len(result)ANDword < result).
- Update if
- Return
resultafter checking all words.
Complexity Analysis
- Time: , where is the number of words in the dictionary and is the length of string
s. In each iteration, we traverses(or a portion of it) to verify subsequence existence. Given constraints (), this runs well within typical time limits (~1 second). - Space: auxiliary space, excluding the input storage and output string. We only use a few integer pointers for traversal.
Solution
def findLongestWord(s: str, dictionary: list[str]) -> str:
result = "" # Default to empty if no valid word found
def is_subsequence(word):
"""Check if 'word' can be formed by deleting characters from s."""
i_s, i_word = 0, 0
while i_s < len(s) and i_word < len(word):
if s[i_s] == word[i_word]:
i_word += 1
# Always advance pointer for source string 's' to find next char match
i_s += 1
return i_word == len(word)
for word in dictionary:
if is_subsequence(word):
# Check length first, then lexicographical order for ties
if (len(result) < len(word)) or \
(len(result) == len(word) and result > word):
result = word
return result
# Example usage matching problem description:
# print(findLongestWord("abpcplea", ["ale","apple","monkey","plea"])) # Output: "apple"
Edge Cases Handled
- No Matches: If no dictionary words are subsequences of
s, the loop finishes and returns the initial empty string. - Tie-Breaking Logic: The condition
(len(result) == len(word) and result > word)ensures that if two valid words have identical lengths, we keep the one appearing earlier in alphabetical order (e.g., “apple” over “apply”). - Short Source String: If
sis shorter than a dictionary word, the subsequence check naturally fails becausei_wordwill never reachlen(word). - Single Character Words: The logic holds regardless of string length; pointers handle single characters correctly.