Course4all
Join us on telegram
Home/dsa/Trie/Longest Word in Dictionary through Deleting

Longest Word in Dictionary through Deleting

Master this topic with zero to advance depth.

Longest Word in Dictionary through Deleting

Given a string s and a string dictionary dictionary, return the longest string in the dictionary that can be formed by deleting some characters of the given string s.

Medium

Examples

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

Level I: Two Pointers (Standard Search)

Intuition

Iterate through each word in the dictionary. Use two pointers to check if the word is a subsequence of s. Keep track of the longest word found (using lexicographical order for ties).

⏱ O(N * L) where N is dict size.💾 O(1).
java
class Solution {
    public String findLongestWord(String s, List<String> dictionary) {
        String result = "";
        for (String word : dictionary) {
            if (isSubsequence(word, s)) {
                if (word.length() > result.length() || (word.length() == result.length() && word.compareTo(result) < 0)) result = word;
            }
        }
        return result;
    }
    private boolean isSubsequence(String word, String s) {
        int i = 0, j = 0;
        while (i < word.length() && j < s.length()) {
            if (word.charAt(i) == s.charAt(j)) i++;
            j++;
        }
        return i == word.length();
    }
}
Approach 2

Level III: Trie (Index-based Subsequence Search)

Intuition

Store s in a way that allows fast subsequence checks. For each character a-z, store a list of indices where it appears in s. For any word, use binary search to find the smallest valid index for the next character. A Trie of words can also be used to explore multiple words simultaneously.

⏱ O(N * L * log S).💾 O(S).
java
import java.util.*;
class Solution {
    public String findLongestWord(String s, List<String> dictionary) {
        String res = "";
        for (String w : dictionary) {
            if (isSub(s, w)) {
                if (w.length() > res.length() || (w.length() == res.length() && w.compareTo(res) < 0)) res = w;
            }
        }
        return res;
    }
    private boolean isSub(String s, String w) {
        int i = 0, j = 0;
        while (i < s.length() && j < w.length()) { if (s.charAt(i) == w.charAt(j)) j++; i++; }
        return j == w.length();
    }
}
← Previous QuestionStream of Characters
Next Question →Prefix and Suffix Search (Optimized Query)