Longest Word in Dictionary through Deleting: Two-Pointer Subsequence Check

Longest Word in Dictionary through Deleting is LeetCode #524. You are given a string s and an array of strings dictionary. Find the longest string in the dictionary that can be formed by deleting some characters of s. If there are multiple results with the same length, return the one that is lexicographically smallest. If no valid word exists, return an empty string.

The problem

Given a string s and a list of candidate words, you need to find which word from the list is the longest subsequence of s. A subsequence means you can delete characters from s (without reordering the remaining ones) and arrive at the target word.

s = "abpcle"
dictionary = ["ale", "apple", "monkey", "plea"]
# Output: "ale"

s = "abpcle"
dictionary = ["a", "b", "c"]
# Output: "a"

In the first example, both "ale" and "plea" are subsequences of "abpcle", but "ale" is not longer than "plea". Wait, they are the same length (3), so you pick the lexicographically smaller one: "ale". Note that "apple" is not a subsequence because s only has one "p".

The key insight

You can check whether a word is a subsequence of s using two pointers in O(n) time. Walk pointer i through s and pointer j through the candidate word. Whenever the characters match, advance both. When they do not match, advance only i. If j reaches the end of the word, that word is a valid subsequence.

The trick is deciding which word to return when multiple words qualify. Instead of tracking the best result manually, sort the dictionary first: longest words first, and for ties, lexicographically smallest first. Then the first word that passes the subsequence check is your answer.

The solution

def findLongestWord(s: str, dictionary: list[str]) -> str:
    dictionary.sort(key=lambda w: (-len(w), w))
    for word in dictionary:
        i = 0
        for char in s:
            if i < len(word) and char == word[i]:
                i += 1
        if i == len(word):
            return word
    return ""

1. Sort the dictionary so longer words come first. Among words of equal length, sort alphabetically.
2. For each word, use a pointer i that tracks how many characters of the word you have matched so far.
3. Walk through every character in s. If the current character matches word[i], increment i.
4. After scanning all of s, if i equals the length of the word, every character was found in order, so the word is a subsequence.
5. Return the first word that passes this check. If none pass, return an empty string.

Step-by-step walkthrough

Let's trace through s = "abpcle" and dictionary = ["ale", "apple", "monkey", "plea", "apply"]. After sorting by (-len, word), the order becomes ["apple", "apply", "ale", "monkey", "plea"]. We check each word against s using two pointers.

The algorithm tried "apple" and "apply" first because they were the longest (5 characters). Both failed because s only contains one "p". Then "ale" (3 characters, lex smallest among 3-letter candidates) passed the subsequence check, so it was returned immediately without needing to check "monkey" or "plea".

Complexity analysis

Time: O(n * k + m * k * log k) where n is the length of s, k is the number of words in the dictionary, and m is the average word length. Sorting the dictionary costs O(k * m * log k) for string comparisons. Then for each of the k words, the subsequence check scans through s once in O(n) time.

Space: O(log k) for the sorting algorithm's internal stack. The subsequence check uses only a constant amount of extra space (the pointer i).

The building blocks

Two-pointer subsequence check

def is_subsequence(word: str, s: str) -> bool:
    i = 0
    for char in s:
        if i < len(word) and char == word[i]:
            i += 1
    return i == len(word)

This pattern appears whenever you need to verify that one string is a subsequence of another. Pointer i only advances when there is a character match, while the scan through s always advances. This guarantees you find characters in order without backtracking.

Custom sort key for priority

dictionary.sort(key=lambda w: (-len(w), w))

Sorting with a tuple key lets you define multi-level priority. The negative length ensures longer words sort first. The word itself as the second element handles the tiebreaker: among equal-length words, Python sorts strings lexicographically. This pattern is useful any time you need to process candidates in a specific priority order.

Edge cases

Empty dictionary. If the dictionary has no words, there is nothing to check. Return "".

No word is a subsequence. If every word in the dictionary contains characters not in s or requires characters in a different order, none will pass the check. The loop finishes and you return "".

Multiple words with the same length. The sort handles this automatically. Words of equal length are ordered alphabetically, so the first one that passes the subsequence check is the lexicographically smallest valid word of that length.

Single-character words. A word like "a" is a subsequence of s as long as "a" appears anywhere in s. The two-pointer check handles this correctly since it only needs one match.

Word longer than s. If a dictionary word is longer than s, it cannot possibly be a subsequence. The pointer i will never reach the end of the word. You could add an early skip for this, but the two-pointer check naturally handles it without special casing.

From understanding to recall

The solution to this problem combines two common patterns: custom sorting and two-pointer subsequence checking. Individually, both are simple. The challenge under interview pressure is remembering to combine them and getting the sort key right. Was it (-len(w), w) or (len(w), w)? The negative sign is easy to forget, and getting it wrong means you check shortest words first, which gives the wrong answer.

Spaced repetition helps lock in these details. When you practice this problem a few days apart, you rebuild the solution from scratch each time. The sort key, the pointer logic, and the early return pattern all become automatic. After a few reps, you stop thinking about whether it should be negative length and simply write it correctly.

Related posts

• Is Subsequence - The core two-pointer subsequence check used as a subroutine in this problem
• Longest Uncommon Subsequence II - Another problem combining subsequence checks with dictionary filtering
• Longest Common Subsequence - A dynamic programming approach to finding shared subsequences between two strings

Master the two-pointer subsequence check and you will have a tool that applies to dozens of string problems.