Domain 2MediumCORE

Longest Word in Dictionary through Deleting

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.

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Two Pointers#Sort

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:

  1. We want the one with the maximum length.
  2. If there’s a tie in length, we pick the lexicographically smallest string (e.g., “apple” over “apply”).
  3. 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 O(N⋅L)O(N \cdot L) solution is acceptable (NN = dict size, LL = 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 N=1000N=1000 and length ≈1000\approx 1000, performing this check for all words is computationally feasible (∼106\sim 10^6 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:

  1. If the current word is valid in s:
    • Is it longer than len(result)? Yes -> Update result.
    • No, but same length? Check if current_word < result (lexicographically). Yes -> Update result.

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

  1. Initialize result as an empty string (""). This handles the “no match” case automatically since we only overwrite if conditions are met.
  2. Iterate through each word in dictionary.
  3. For each word, use a two-pointer technique to check subsequence validity:
    • Pointer i for source string s, pointer j for current dictionary word.
    • Advance both pointers if characters match; advance only i otherwise until we find the character or reach end of s.
  4. If valid, compare with result:
    • Update if len(word) > len(result) OR (len(word) == len(result) AND word < result).
  5. Return result after checking all words.

Complexity Analysis

  • Time: O(N⋅L)O(N \cdot L), where NN is the number of words in the dictionary and LL is the length of string s. In each iteration, we traverse s (or a portion of it) to verify subsequence existence. Given constraints (103×103=10610^3 \times 10^3 = 10^6), this runs well within typical time limits (~1 second).
  • Space: O(1)O(1) 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 s is shorter than a dictionary word, the subsequence check naturally fails because i_word will never reach len(word).
  • Single Character Words: The logic holds regardless of string length; pointers handle single characters correctly.