LeetCode 524: Longest Word in Dictionary through Deleting

Problem Restatement

We are given:

s
dictionary

We may delete some characters from s.

We need to return the longest string in dictionary that can be formed as a subsequence of s.

If multiple answers have the same length, return the lexicographically smallest one.

If no dictionary word can be formed, return the empty string.

The official problem asks us to find the longest dictionary word obtainable by deleting characters from s. If several answers have the same length, choose the lexicographically smallest one. (leetcode.com)

Input and Output

Function shape:

class Solution:
    def findLongestWord(
        self,
        s: str,
        dictionary: List[str]
    ) -> str:
        ...

Examples

Example 1:

s = "abpcplea"
dictionary = ["ale", "apple", "monkey", "plea"]

Possible subsequences include:

The longest valid word is:

apple

So the answer is:

"apple"

Example 2:

s = "abpcplea"
dictionary = ["a", "b", "c"]

All words have length 1.

The lexicographically smallest is:

a

So the answer is:

"a"

First Thought: Test Every Dictionary Word

For each dictionary word:

1. Check whether it is a subsequence of s
2. Keep the best valid candidate

This works because the dictionary size is manageable.

The main subproblem is efficient subsequence checking.

Key Insight

Use two pointers.

To check whether word w is a subsequence of s:

1. Scan through s
2. Advance a pointer in w whenever characters match
3. If all characters of w are matched, then w is a subsequence

Example:

s = "abpcplea"
w = "apple"

Matching process:

All characters were matched.

So "apple" is a subsequence.

Choosing the Best Candidate

Suppose several words are valid subsequences.

We prefer:

1. Larger length
2. Lexicographically smaller if lengths are equal

So for candidate word, update the answer if:

len(word) > len(answer)

or:

len(word) == len(answer)
and word < answer

Algorithm

Initialize:

answer = ""

For each word in dictionary:

1. Check whether it is a subsequence of s
2. If valid:
   • update answer if the word is longer
   • or if same length but lexicographically smaller

Return answer.

Correctness

The helper function correctly determines whether a dictionary word is a subsequence of s by scanning s left to right and matching characters in order.

A word is considered valid exactly when all of its characters can be matched in sequence inside s.

The algorithm checks every dictionary word, so every valid candidate is considered.

The update rule always keeps the best candidate according to the problem ordering:

1. Prefer larger length
2. For equal lengths, prefer lexicographically smaller words

Therefore, after processing the entire dictionary, answer is exactly the required output.

If no word is a subsequence of s, the answer remains the empty string, which is correct.

Complexity

Let:

More precisely, the total work is proportional to all subsequence checks.

Implementation

from typing import List

class Solution:
    def findLongestWord(
        self,
        s: str,
        dictionary: List[str]
    ) -> str:

        def is_subsequence(word: str) -> bool:
            i = 0

            for ch in s:
                if i < len(word) and word[i] == ch:
                    i += 1

            return i == len(word)

        answer = ""

        for word in dictionary:
            if is_subsequence(word):
                if (
                    len(word) > len(answer)
                    or (
                        len(word) == len(answer)
                        and word < answer
                    )
                ):
                    answer = word

        return answer

Code Explanation

The helper function checks subsequences:

def is_subsequence(word: str) -> bool:

i tracks how many characters of word have been matched:

i = 0

Scan through s:

for ch in s:

Advance the pointer when characters match:

if i < len(word) and word[i] == ch:
    i += 1

If all characters were matched:

return i == len(word)

then the word is a subsequence.

Now process every dictionary word:

for word in dictionary:

If it is valid:

if is_subsequence(word):

update the answer if:

len(word) > len(answer)

or if lengths tie and the new word is lexicographically smaller:

word < answer

Testing

def test_find_longest_word():
    s = Solution()

    assert (
        s.findLongestWord(
            "abpcplea",
            ["ale", "apple", "monkey", "plea"]
        )
        == "apple"
    )

    assert (
        s.findLongestWord(
            "abpcplea",
            ["a", "b", "c"]
        )
        == "a"
    )

    assert (
        s.findLongestWord(
            "bab",
            ["ba", "ab", "a", "b"]
        )
        == "ab"
    )

    assert (
        s.findLongestWord(
            "abc",
            ["d", "e"]
        )
        == ""
    )

    assert (
        s.findLongestWord(
            "aaa",
            ["aa", "aaa", "aaaa"]
        )
        == "aaa"
    )

    print("all tests passed")

Test meaning: