Problem Statement
Given a lowercase string s and a dictionary d[] containing lowercase words, find the longest word in the dictionary that can be obtained by deleting some characters from s without changing the order of the remaining characters.
If multiple words have the same maximum length, return the lexicographically smallest word.
If no dictionary word can be formed from s, return an empty string.
Example 1
s = "abpcplea"
d = ["ale", "apple", "monkey", "plea"]
Output:
apple
Explanation
We can obtain "apple" from "abpcplea" by deleting characters while keeping the remaining characters in the same order.
abpcplea
↓
apple
"monkey" cannot be formed because its characters do not occur in the required order.
Understanding the Concept: Subsequence
The important concept in this problem is Subsequence.
A string word is a subsequence of s if we can delete zero or more characters from s and obtain word.
The important rule is:
The order of the characters must remain unchanged.
For example:
s = "abcde"
These are subsequences:
ace
abd
abc
de
a
But this is not a subsequence:
eca
Although e, c, and a exist in s, their order is different.
Simple Approach
One straightforward solution is to check every dictionary word and determine whether it is a subsequence of s.
For example:
s = "abpcplea"
word = "apple"
We scan s and try to match:
a → p → p → l → e
If all characters are found in order, the word is valid.
However, s can contain up to:
5 * 10^5
characters.
The dictionary can contain:
10^4
words.
So repeatedly scanning the complete string s for every dictionary word can be inefficient.
We need a faster way.
Optimized Approach
We preprocess the string s.
For every character from a to z, we store all the positions where that character occurs.
For example:
s = "abpcplea"
The positions are:
a → [0, 7]
b → [1]
c → [3]
e → [6]
l → [5]
p → [2, 4]
Now suppose we want to check:
word = "apple"
We need to find:
a
p
p
l
e
in that order.
We can use the stored positions and binary search to quickly find the next valid position.
Why Binary Search?
Suppose we have:
p → [2, 4]
After matching a at position 0, we need to find a p after position 0.
Binary search gives:
2
After matching the first p at position 2, we need another p after position 2.
Binary search gives:
4
Then we continue with l and e.
This allows us to find the next character without scanning the entire string.
Algorithm
The algorithm consists of two main steps.
Step 1: Store Character Positions
Create an array of 26 lists:
List<Integer>[] positions = new ArrayList[26];
Each list represents one lowercase character.
For example:
positions[0] → positions of 'a'
positions[1] → positions of 'b'
positions[2] → positions of 'c'
...
positions[25] → positions of 'z'
Then scan s once and store every character's index.
for (int i = 0; i < s.length(); i++) {
positions[s.charAt(i) - 'a'].add(i);
}
The expression:
s.charAt(i) - 'a'
converts a character into an index.
For example:
'a' - 'a' = 0
'b' - 'a' = 1
'c' - 'a' = 2
Step 2: Check Every Dictionary Word
For every word in the dictionary, check whether it is a subsequence of s.
for (String word : d) {
if (isSubsequence(word, positions)) {
...
}
}
If the word is a valid subsequence, compare it with the current answer.
Choosing the Answer
There are two conditions.
Condition 1: Longer word
If the current word is longer:
word.length() > answer.length()
then update the answer.
Condition 2: Same length
If both words have the same length, choose the lexicographically smaller word.
word.compareTo(answer) < 0
For example:
"apple"
"ale"
apple is longer, so we choose:
apple
If we have:
"abc"
"abd"
Both have length 3.
Lexicographically:
abc < abd
Therefore:
abc
is selected.
Checking Whether a Word Is a Subsequence
The important method is:
private boolean isSubsequence(String word,
List<Integer>[] positions)
We maintain:
int previousIndex = -1;
This represents the position of the previously matched character.
Initially:
previousIndex = -1
because we have not matched anything.
For every character in word, we find its first occurrence after previousIndex.
int index = upperBound(list, previousIndex);
If no position is available:
if (index == list.size()) {
return false;
}
Otherwise, update:
previousIndex = list.get(index);
Understanding upperBound()
This is the most important part of the solution.
We need to find:
The first position whose value is greater than previousIndex.
For example:
positions of 'p' = [2, 4]
If:
previousIndex = 0
we need:
2
If:
previousIndex = 2
we need:
4
If:
previousIndex = 4
there is no valid position.
So upperBound() finds the first value:
value > target
Binary Search Implementation
private int upperBound(List<Integer> list, int target) {
int low = 0;
int high = list.size();
while (low < high) {
int mid = low + (high - low) / 2;
if (list.get(mid) <= target) {
low = mid + 1;
} else {
high = mid;
}
}
return low;
}
Let's understand this step by step.
Initially:
low = 0;
high = list.size();
Calculate the middle:
int mid = low + (high - low) / 2;
This is preferred over:
(low + high) / 2
because it avoids integer overflow for very large values.
Then:
if (list.get(mid) <= target)
means the current position is not suitable because we need a position strictly greater than target.
Therefore:
low = mid + 1;
Otherwise, the current position may be the answer:
high = mid;
When the loop finishes:
low == high
and low is the first position greater than target.
Complete Java Code
import java.util.*;
class Solution {
public String findLongestWord(String s, List<String> d) {
// Store positions of every character in s
List<Integer>[] positions = new ArrayList[26];
for (int i = 0; i < 26; i++) {
positions[i] = new ArrayList<>();
}
// Store indices of each character
for (int i = 0; i < s.length(); i++) {
positions[s.charAt(i) - 'a'].add(i);
}
String answer = "";
// Check every dictionary word
for (String word : d) {
if (isSubsequence(word, positions)) {
// Prefer longer word
// If same length, prefer lexicographically smaller word
if (word.length() > answer.length()
|| (word.length() == answer.length()
&& word.compareTo(answer) < 0)) {
answer = word;
}
}
}
return answer;
}
private boolean isSubsequence(String word,
List<Integer>[] positions) {
int previousIndex = -1;
for (char ch : word.toCharArray()) {
List<Integer> list = positions[ch - 'a'];
// Find first position greater than previousIndex
int index = upperBound(list, previousIndex);
// Character cannot be found
if (index == list.size()) {
return false;
}
// Update the last matched position
previousIndex = list.get(index);
}
return true;
}
// Find first value greater than target
private int upperBound(List<Integer> list, int target) {
int low = 0;
int high = list.size();
while (low < high) {
int mid = low + (high - low) / 2;
if (list.get(mid) <= target) {
low = mid + 1;
} else {
high = mid;
}
}
return low;
}
}
Dry Run
Consider:
s = "abpcplea"
word = "apple"
Character positions:
a → [0, 7]
p → [2, 4]
l → [5]
e → [6]
Now match "apple".
Match a
previousIndex = -1
First a after -1:
0
So:
previousIndex = 0
Match first p
Find p > 0:
2
Now:
previousIndex = 2
Match second p
Find p > 2:
4
Now:
previousIndex = 4
Match l
Find l > 4:
5
Match e
Find e > 5:
6
All characters were successfully matched.
Therefore:
apple
is a valid subsequence.
Why Greedy Matching Works
For each character, we always select the earliest possible occurrence after the previous character.
For example:
p → [2, 4]
If we need a p, choosing position 2 is always better than choosing position 4.
Why?
Because choosing an earlier position leaves more characters available for the remaining part of the word.
This greedy strategy therefore correctly determines whether the word can be formed as a subsequence.
Complexity Analysis
Let:
N = length of s
n = number of dictionary words
m = maximum dictionary word length
Time Complexity
Building the position lists:
O(N)
For every dictionary word, each character requires a binary search:
O(log N)
A word has at most m characters.
Therefore:
O(n × m × log N)
Overall:
O(N + n × m × log N)
This matches the expected complexity.
Auxiliary Space
We store the position of every character in s.
There are N total stored positions.
Therefore:
O(N)
Important Java Concepts Used
1. Generic Array
We create:
List<Integer>[] positions = new ArrayList[26];
This represents 26 lists, one for every lowercase English character.
2. Character to Index Conversion
ch - 'a'
converts a character into an array index.
For example:
'a' → 0
'b' → 1
'z' → 25
This is useful when working with lowercase English alphabets.
3. compareTo()
We use:
word.compareTo(answer) < 0
to perform lexicographical comparison.
For example:
"abc".compareTo("abd")
returns a negative value because "abc" comes before "abd".
4. Binary Search
Binary search reduces the search time from:
O(N)
to:
O(log N)
This is particularly important because the original string can contain up to 500,000 characters.
Alternative Simple Solution
There is also a simpler two-pointer approach.
For each dictionary word, scan s from left to right:
private boolean isSubsequence(String word, String s) {
int i = 0;
int j = 0;
while (i < s.length() && j < word.length()) {
if (s.charAt(i) == word.charAt(j)) {
j++;
}
i++;
}
return j == word.length();
}
This is easier to understand, but each dictionary word may require scanning a large portion of s.
The position + binary-search approach is better suited to the given constraints and expected complexity.
Final Takeaway
The key idea is:
Dictionary word
↓
Is it a subsequence of s?
↓
Use precomputed character positions
↓
Use binary search to find the next position
↓
If valid, compare length
↓
If same length, compare lexicographically
↓
Return the answer
The three concepts to remember from this problem are:
Subsequence — characters must appear in the same order.
Position preprocessing — store where every character occurs.
Upper-bound binary search — quickly find the next valid character position.
This combination allows the solution to handle a very large input string efficiently.
Join the conversation! Your thoughts help the community grow.