#524

Medium

auto_awesomeTwo-pointer scanning with invariant tracking

LeetCode Problem Workspace

Longest Word in Dictionary through Deleting

Find the longest word in the dictionary that can be formed by deleting characters from a string, using two-pointer scanning.

array two pointers string sorting

Problem Statement

You are given a string s and a list of strings dictionary. Your task is to find the longest string in dictionary that can be formed by deleting some characters from s. If multiple words meet the criteria, return the one with the smallest lexicographical order. If no word in the dictionary can be formed, return an empty string.

The input string s and the words in dictionary consist of only lowercase English letters. The task should be solved efficiently, considering both time and space complexities, given that the string length and dictionary size can go up to 1000.

Examples

Example 1

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

Output: "apple"

Example details omitted.

Example 2

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

Output: "a"

Example details omitted.

Constraints

1 <= s.length <= 1000
1 <= dictionary.length <= 1000
1 <= dictionary[i].length <= 1000
s and dictionary[i] consist of lowercase English letters.

Solution Approach

Two-Pointer Scanning

The two-pointer approach is essential for this problem. One pointer traverses the string s while the other pointer scans through each word in the dictionary. For each word, you move the pointer on s to check if the word can be formed by deleting characters in s.

Tracking Valid Words

To efficiently track the longest valid word, maintain a variable to store the longest word found. During the two-pointer traversal, whenever a word is valid (i.e., can be formed by deleting characters), compare its length to the current longest word. If it's longer or lexicographically smaller, update the result.

Early Termination Optimization

You can optimize the solution by stopping early when a word is found that is the longest possible, reducing unnecessary checks for smaller dictionary words.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity depends on the number of dictionary words and the length of s. For each word in the dictionary, you scan through s with two pointers, resulting in a time complexity of O(n * m), where n is the length of s and m is the average length of the dictionary words. Space complexity is O(1), since only a few pointers and variables are used.

What Interviewers Usually Probe

Check if the candidate effectively uses two-pointer scanning to match characters between s and dictionary words.
Look for optimization strategies, especially how they handle lexicographical order and early termination.
Assess how the candidate handles edge cases, such as when no words can be formed from s.

Common Pitfalls or Variants

Common pitfalls

Failing to account for lexicographical order when multiple words of the same length are valid.
Not using the two-pointer method efficiently, leading to unnecessary scans of s.
Overcomplicating the problem with excessive nested loops instead of leveraging simple pointer movement.

Follow-up variants

The problem could be extended to handle uppercase letters or include non-English characters in the string and dictionary.
A variant could involve finding the second longest valid word if the longest one has multiple occurrences.
The task might be modified to allow for insertion or replacement of characters instead of only deletions.

FAQ

What is the two-pointer approach in the context of the Longest Word in Dictionary through Deleting problem?

In this problem, the two-pointer approach involves using one pointer to traverse the string s and another pointer to track each dictionary word, checking if characters can be deleted to form the word.

How can I optimize the solution for the problem 'Longest Word in Dictionary through Deleting'?

You can optimize by using early termination when you find the longest valid word or by eliminating unnecessary checks for words that are shorter than the current longest valid word.

What are common mistakes when solving 'Longest Word in Dictionary through Deleting'?

Common mistakes include neglecting lexicographical order, inefficient scanning with nested loops, and not handling edge cases where no words can be formed.

How does lexicographical order affect the solution to this problem?

If multiple words can be formed from s, lexicographical order is used to return the smallest one. This ensures that among equally long valid words, the word that appears first alphabetically is returned.

Can the two-pointer approach be applied to other string-related problems?

Yes, the two-pointer approach is widely used for problems involving string matching, subsequences, or partitions, where elements need to be compared or scanned in parallel.

terminal

Solution

Solution 1: Subsequence Judgment

We define a function $check(s, t)$ to determine whether string $s$ is a subsequence of string $t$. We can use a two-pointer approach, initializing two pointers $i$ and $j$ to point to the beginning of strings $s$ and $t$ respectively, then continuously move pointer $j$. If $s[i]$ equals $t[j]$, then move pointer $i$. Finally, check if $i$ equals the length of $s$. If $i$ equals the length of $s$, it means $s$ is a subsequence of $t$.

class Solution:
    def findLongestWord(self, s: str, dictionary: List[str]) -> str:
        def check(s: str, t: str) -> bool:
            m, n = len(s), len(t)
            i = j = 0
            while i < m and j < n:
                if s[i] == t[j]:
                    i += 1
                j += 1
            return i == m

        ans = ""
        for t in dictionary:
            if check(t, s) and (len(ans) < len(t) or (len(ans) == len(t) and ans > t)):
                ans = t
        return ans

Continue Practicing

#522 longest uncommon subsequence ii #1048 longest string chain #532 k diff pairs in an array