Longest Word in Dictionary through Deleting solution and explanation
Google
9 more videos on this problem
Longest Word in Dictionary through Deleting | Live Coding with Explanation | Leetcode - 524Algorithms Made Easy · 9:49 · 6K views
Leetcode - Longest Word in Dictionary through Deleting (Python)Timothy H Chang · 5:33 · 2K views
Longest Word in Dictionary through Deleting | LeetCode 524 | StirngNaresh Gupta · 8:48 · 1K views
524. Longest Word in Dictionary through Deleting (Leetcode Medium)Programming Live with Larry · 18:30 · 852 views
Leetcode [524] Longest Word in Dictionary through DeletingSDE Skills · 15:02 · 597 views
Longest Word in Dictionary through Deleting | LeetCode 524 | Coders CampCoders Camp · 19:36 · 453 views
524 Longest Word in Dictionary through Deleting | Leetcode daily challenge | FAANG interviewsTech DEV Coding · 10:00 · 339 views
Daily Leetcode #328: Feb 22, 2021 - 524. Longest Word in Dictionary through DeletingProgramming Live with Larry · 19:38 · 324 views
Leetcode 524 Longest Word in Dictionary through Deleting - 2 Pointers ApproachAlgorithmicIQ · 20:16 · 272 views
Longest Word in Dictionary through Deleting | LeetCode 524The Code Architect · 8:36 · 184 views
The problem
Given a string s and a string array dictionary, return the longest string in the dictionary that can be formed by deleting some of the given string characters. If there is more than one possible result, return the longest word with the smallest lexicographical order. If there is no possible result, return the empty string.
Example 1:
Input: s = "abpcplea", dictionary = ["ale","apple","monkey","plea"] Output: "apple"
Example 2:
Input: s = "abpcplea", dictionary = ["a","b","c"] Output: "a"
Constraints:
1 <= s.length <= 10001 <= dictionary.length <= 10001 <= dictionary[i].length <= 1000sanddictionary[i]consist of lowercase English letters.
Approach overview
Problem Overview: Given a string s and a list of dictionary words, find the longest word that can be formed by deleting some characters from s. The resulting word must be a subsequence of s. If multiple words have the same maximum length, return the lexicographically smallest one.
Approach 1: Two-Pointer Technique (Time: O(n * m), Space: O(1))
This approach checks whether each dictionary word is a subsequence of s. Use two pointers: one for the main string and one for the candidate word. Iterate through s while advancing the second pointer whenever characters match. If the pointer for the dictionary word reaches its end, the word is a valid subsequence. Track the best result by comparing lengths first and lexicographic order second. The idea relies on efficient linear scanning rather than generating all subsequences, which would be exponential. This method is simple, memory-efficient, and works well when the dictionary size is moderate.
Since each subsequence check scans s, the complexity becomes O(D * |s|) where D is the number of dictionary words. Only a few variables are stored, so space remains O(1). This approach frequently appears in problems involving Two Pointers and String traversal.
Approach 2: Sorting and Checking (Time: O(D log D + D * |s|), Space: O(1) or O(D) depending on sort)
Another strategy sorts the dictionary first, prioritizing longer words and breaking ties using lexicographical order. After sorting, iterate through the dictionary and check each word using the same two-pointer subsequence check. The first valid word found is immediately the correct answer because the ordering guarantees maximum length and smallest lexicographic value.
Sorting costs O(D log D), and each subsequence verification still costs O(|s|). The advantage is early termination: you often stop after checking only a few words. This makes the method practical when the dictionary is large but contains many short candidates. The approach combines ideas from Array traversal and Sorting with subsequence validation.
Recommended for interviews: The two-pointer subsequence check is the core technique interviewers expect. It shows you recognize the subsequence pattern and can implement it efficiently in linear time. Sorting the dictionary first is a useful optimization that demonstrates awareness of lexicographic constraints and early stopping. A strong solution explains the two-pointer subsequence logic clearly and then discusses sorting as a practical improvement.
Approach 1: Two-Pointer Technique
This approach involves using a two-pointer technique to check if a string from the dictionary is a subsequence of the given string s. We iterate through each word in the dictionary and for each word, use two pointers to traverse through the word and s. If all characters of the word are found in the same order in s, then it's a valid word. We maintain a result variable to track the longest valid word found so far, and if multiple are of the same length, we track the smallest lexicographical order.
def is_subsequence(s, word):
it = iter(s)
return all(char in it for char in word)
def find_longest_word(s, dictionary):
dictionary.sort(key=lambda x: (-len(x), x))
for word in dictionary:
if is_subsequence(s, word):
return word
return ""
s = "abpcplea"
dictionary = ["ale", "apple", "monkey", "plea"]
print(find_longest_word(s, dictionary))import java.util.List;
public class LongestWordFinder {
public String findLongestWord(String s, List<String> dictionary) {
String longest = "";
for (String word : dictionary) {
if (isSubsequence(s, word)) {
if (word.length() > longest.length() || (word.length() == longest.length() && word.compareTo(longest) < 0)) {
longest = word;
}
}
}
return longest;
}
private boolean isSubsequence(String s, String word) {
int i = 0, j = 0;
while (i < s.length() && j < word.length()) {
if (s.charAt(i) == word.charAt(j)) {
j++;
}
i++;
}
return j == word.length();
}
public static void main(String[] args) {
LongestWordFinder finder = new LongestWordFinder();
String s = "abpcplea";
List<String> dictionary = List.of("ale", "apple", "monkey", "plea");
System.out.println(finder.findLongestWord(s, dictionary));
}
}#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
bool isSubsequence(const string &s, const string &word) {
int i = 0, j = 0;
while (i < s.size() && j < word.size()) {
if (s[i] == word[j]) {
j++;
}
i++;
}
return j == word.size();
}
string findLongestWord(string s, vector<string>& dictionary) {
string result = "";
for (const string &word : dictionary) {
if (isSubsequence(s, word)) {
if (word.size() > result.size() || (word.size() == result.size() && word < result)) {
result = word;
}
}
}
return result;
}
int main() {
string s = "abpcplea";
vector<string> dictionary = {"ale", "apple", "monkey", "plea"};
cout << findLongestWord(s, dictionary) << endl;
return 0;
}function isSubsequence(s, word) {
let i = 0, j = 0;
while (i < s.length && j < word.length) {
if (s[i] === word[j]) {
j++;
}
i++;
}
return j === word.length;
}
function findLongestWord(s, dictionary) {
let longest = "";
for (let word of dictionary) {
if (isSubsequence(s, word)) {
if (word.length > longest.length || (word.length === longest.length && word < longest)) {
longest = word;
}
}
}
return longest;
}
const s = "abpcplea";
const dictionary = ["ale", "apple", "monkey", "plea"];
console.log(findLongestWord(s, dictionary));#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int isSubsequence(char *s, char *word) {
int i = 0, j = 0;
while (i < strlen(s) && j < strlen(word)) {
if (s[i] == word[j]) {
j++;
}
i++;
}
return j == strlen(word);
}
char *findLongestWord(char *s, char **dictionary, int dictionarySize) {
char *result = "";
for (int i = 0; i < dictionarySize; i++) {
char *word = dictionary[i];
if (isSubsequence(s, word)) {
if (strlen(word) > strlen(result) || (strlen(word) == strlen(result) && strcmp(word, result) < 0)) {
result = word;
}
}
}
return result;
}
int main() {
char *s = "abpcplea";
char *dictionary[] = {"ale", "apple", "monkey", "plea"};
printf("%s\n", findLongestWord(s, dictionary, 4));
return 0;
}using System;
using System.Collections.Generic;
public class LongestWordFinder {
public string FindLongestWord(string s, IList<string> dictionary) {
string result = "";
foreach (string word in dictionary) {
if (IsSubsequence(s, word)) {
if (word.Length > result.Length || (word.Length == result.Length && string.Compare(word, result) < 0)) {
result = word;
}
}
}
return result;
}
private bool IsSubsequence(string s, string word) {
int i = 0, j = 0;
while (i < s.Length && j < word.Length) {
if (s[i] == word[j]) {
j++;
}
i++;
}
return j == word.Length;
}
public static void Main(string[] args) {
LongestWordFinder finder = new LongestWordFinder();
string s = "abpcplea";
IList<string> dictionary = new List<string> { "ale", "apple", "monkey", "plea" };
Console.WriteLine(finder.FindLongestWord(s, dictionary));
}
}The Python solution uses the is_subsequence function to check if a word is a subsequence of s by comparing each character using iterators. The dictionary is first sorted by length in descending order and lexicographically, to ensure the longest and smallest lexicographically word is selected first. Then check each word for subsequence conditions.
- Time Complexity: O(n * m + n log n), due to sorting the dictionary and checking subsequence for each word, where n is the length of the dictionary, and m is the length of string
s. - Space Complexity: O(1), considering auxiliary space aside from input.
Approach 2: Sorting and Checking
This approach involves sorting the dictionary by length (descending) and lexicographical order (ascending). By sorting first, you can ensure that you are checking the longest available words first while resolving ties based on the smallest alphabetical order. We then iterate through this sorted list and use a function to check if a word is a valid subsequence of s.
def is_subsequence(s, word):
it = iter(s)
return all(char in it for char in word)
def find_longest_word(s, dictionary):
# Sort dictionary by length descending, then lexicographically
dictionary.sort(key=lambda x: (-len(x), x))
for word in dictionary:
if is_subsequence(s, word):
return word
return ""
s = "abpcplea"
dictionary = ["ale", "apple", "monkey", "plea"]
print(find_longest_word(s, dictionary))import java.util.List;
import java.util.Collections;
public class LongestWordFinderSorted {
public String findLongestWord(String s, List<String> dictionary) {
// Sort dictionary by length descending, then lexicographically
Collections.sort(dictionary, (a, b) -> a.length() != b.length() ? b.length() - a.length() : a.compareTo(b));
for (String word : dictionary) {
if (isSubsequence(s, word)) {
return word;
}
}
return "";
}
private boolean isSubsequence(String s, String word) {
int i = 0, j = 0;
while (i < s.length() && j < word.length()) {
if (s.charAt(i) == word.charAt(j)) {
j++;
}
i++;
}
return j == word.length();
}
public static void main(String[] args) {
LongestWordFinderSorted finder = new LongestWordFinderSorted();
String s = "abpcplea";
List<String> dictionary = List.of("ale", "apple", "monkey", "plea");
System.out.println(finder.findLongestWord(s, dictionary));
}
}This Python implementation uses sorting to align words by the desirable evaluation order: first longest, then smallest lexicographically. The `is_subsequence` function checks if a word is a subsequence of `s`, as before accomplished using iterators for efficiency.
- Time Complexity: O(n * m + n log n) due to the dictionary sorting and subsequence checking operations, where n is the length of the dictionary, and m is the length of string `s`.
- Space Complexity: O(n), where n is based on sorting operations and storage of the dictionary list.
Approach 3: 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.
We initialize the answer string ans as an empty string. Then, we iterate through each string t in the array dictionary. If t is a subsequence of s, and the length of t is greater than the length of ans, or the length of t is equal to the length of ans but t is lexicographically smaller than ans, then we update ans to t.
The time complexity is O(d times (m + n)), where d is the length of the string list, and m and n are the lengths of string s and the average length of strings in the list, respectively. The space complexity is O(1).
function findLongestWord(s: string, dictionary: string[]): string {
const check = (s: string, t: string): boolean => {
const [m, n] = [s.length, t.length];
let i = 0;
for (let j = 0; i < m && j < n; ++j) {
if (s[i] === t[j]) {
++i;
}
}
return i === m;
};
let ans: string = '';
for (const t of dictionary) {
const [a, b] = [ans.length, t.length];
if (check(t, s) && (a < b || (a === b && ans > t))) {
ans = t;
}
}
return ans;
}func findLongestWord(s string, dictionary []string) string {
ans := ''
check := func(s, t string) bool {
m, n := len(s), len(t)
i := 0
for j := 0; i < m && j < n; j++ {
if s[i] == t[j] {
i++
}
}
return i == m
}
for _, t := range dictionary {
a, b := len(ans), len(t)
if check(t, s) && (a < b || (a == b && ans > t)) {
ans = t
}
}
return ans
}impl Solution {
pub fn find_longest_word(s: String, dictionary: Vec<String>) -> String {
let mut ans = String::new();
for t in dictionary {
let a = ans.len();
let b = t.len();
if Self::check(&t, &s) && (a < b || (a == b && t < ans)) {
ans = t;
}
}
ans
}
fn check(s: &str, t: &str) -> bool {
let (m, n) = (s.len(), t.len());
let mut i = 0;
let mut j = 0;
let s: Vec<char> = s.chars().collect();
let t: Vec<char> = t.chars().collect();
while i < m && j < n {
if s[i] == t[j] {
i += 1;
}
j += 1;
}
i == m
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Two-Pointer Technique |
|
| Sorting and Checking |
|
| Subsequence Judgment | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Two-Pointer Technique | O(D * |s|) | O(1) | General case. Simple subsequence check for each dictionary word without preprocessing. |
| Sorting and Checking | O(D log D + D * |s|) | O(1)–O(D) | When you want early termination by checking longest and lexicographically smallest words first. |
Frequently asked questions
Is Longest Word in Dictionary through Deleting easy or hard?
The problem is rated Medium on LeetCode because it combines multiple ideas: subsequence detection, lexicographic ordering, and careful candidate selection. The implementation is straightforward once you recognize the two-pointer subsequence pattern.
Longest Word in Dictionary through Deleting Python/Java solution
In Python or Java, iterate through each dictionary word and check if it is a subsequence of the string using two indices. Update the best candidate when a longer word is found or when the length is equal but the word is lexicographically smaller. This approach keeps the implementation short and runs in O(D * n) time.
How to solve Longest Word in Dictionary through Deleting in O(n)?
The subsequence check itself runs in O(n) time for a single candidate word using two pointers. One pointer scans the main string while the other scans the dictionary word. In practice, the full problem runs in O(D * n) because the subsequence test must be repeated for multiple dictionary entries.
What is the best approach for Longest Word in Dictionary through Deleting?
The most practical solution uses a two-pointer subsequence check. For each word in the dictionary, scan the main string with one pointer and advance the second pointer when characters match. If the dictionary pointer reaches the end, the word is a valid subsequence. This runs in O(D * |s|) time and O(1) space.
Is Longest Word in Dictionary through Deleting asked at Google/Amazon/Meta?
Variants of subsequence checking and dictionary filtering appear in interviews at companies like Google, Amazon, and Meta. The problem tests string traversal, lexicographic comparison, and efficient scanning using two pointers, which are common interview patterns.
What data structure is used in Longest Word in Dictionary through Deleting?
The core data structures are arrays or lists for the dictionary and simple string traversal with two pointers. Some implementations also use sorting on the dictionary to prioritize longer or lexicographically smaller words before performing subsequence checks.
What is the time complexity of Longest Word in Dictionary through Deleting?
Using the two-pointer approach, each dictionary word requires a linear scan of the string. If the dictionary has D words and the string length is n, the total time complexity is O(D * n). If the dictionary is sorted first to prioritize longer words, an additional O(D log D) sorting cost is added.