Skip to main content
Talentd

Longest Word in Dictionary through Deleting - Solution & Explanation

MediumArrayTwo PointersStringSorting18 min readAsked at: Google, Usaa
Practice this problem

Problem Statement

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 <= 1000
  • 1 <= dictionary.length <= 1000
  • 1 <= dictionary[i].length <= 1000
  • s and dictionary[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.

The solution defines a helper function isSubsequence that determines if a given word is a subsequence of s by using two pointers: one traversing s and the other traversing the word. The main logic iterates through each word in the dictionary and checks if it is a subsequence, updating the result if it is longer or lexicographically smaller than the previous result.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

  • Time Complexity: O(n * m), where n is the length of dictionary and m is the maximum length of any string in the dictionary or the string s. This is because we potentially traverse the entire string for each dictionary word.
  • Space Complexity: O(1), since only a few pointers and variables are used for calculation.
Try this approach in the editor →

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.

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.

Code

PythonJava

Python

Java

Complexity

  • 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.
Try this approach in the editor →

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).

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Two-Pointer Technique
  • Time Complexity: O(n * m), where n is the length of dictionary and m is the maximum length of any string in the dictionary or the string s. This is because we potentially traverse the entire string for each dictionary word.
  • Space Complexity: O(1), since only a few pointers and variables are used for calculation.
Sorting and Checking
  • 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.
Subsequence Judgment—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Two-Pointer TechniqueO(D * |s|)O(1)General case. Simple subsequence check for each dictionary word without preprocessing.
Sorting and CheckingO(D log D + D * |s|)O(1)–O(D)When you want early termination by checking longest and lexicographically smallest words first.

Video Solution

Longest Word in Dictionary through Deleting | Live Coding with Explanation | Leetcode - 524 • Algorithms Made Easy • 6,483 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Longest Word in Dictionary through Deleting with our built-in code editor and test cases.

Practice on FleetCode
Previous

Longest Word in Dictionary