Scale Engineer

Longest Word in Dictionary through Deleting

Med
#0509Time: O(m log m * l + m * n), where `m` is the number of words in the dictionary, `n` is the length of `s`, and `l` is the average length of words in the dictionary. The sorting step takes `O(m log m * l)` due to string comparisons. The iteration and subsequence check takes `O(m * n)` in the worst case. The sorting cost often dominates.Space: O(log m) or O(m) for sorting. In Java, `Collections.sort` for lists uses Timsort which has an auxiliary space complexity of `O(log m)` on average and `O(m)` in the worst case.
Patterns
Two Pointers
Algorithms
Sorting
Data structures
ArrayString

Prompt

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.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach simplifies the selection logic by pre-processing the dictionary. The idea is to sort the dictionary based on the desired criteria: first by decreasing word length, and then by increasing lexicographical order for words of the same length. After sorting, we iterate through the dictionary and the very first word that is a subsequence of the input string s will be the correct answer. This is because any subsequent word will either be shorter or lexicographically larger, thus not a better candidate.

Algorithm

  • Create a custom comparator to sort strings. The comparator should first compare by length in descending order. If lengths are equal, it should compare lexicographically in ascending order. - Sort the dictionary list using this custom comparator. - Iterate through the now-sorted dictionary. - For each word in the dictionary, check if it is a subsequence of s using a helper function isSubsequence. - The isSubsequence function uses a two-pointer technique. One pointer i for s and another j for word. Traverse s. If s.charAt(i) matches word.charAt(j), increment j. Always increment i. The word is a subsequence if j reaches the end of the word. - Since the dictionary is sorted by our desired criteria, the first word found to be a subsequence is the answer. Return it immediately. - If the loop finishes without finding any such word, return an empty string.

Walkthrough

The core idea is to sort the dictionary first so that the first valid word we encounter is guaranteed to be the answer. By sorting by length descending and then lexicographically ascending, we ensure that we check the best possible candidates first. Once a match is found, we can stop searching. ```java import java.util.Collections; import java.util.List;

class Solution { public String findLongestWord(String s, List<String> dictionary) { // Sort the dictionary: longest word first, then lexicographically smallest Collections.sort(dictionary, (a, b) -> { if (a.length() != b.length()) { return b.length() - a.length(); } return a.compareTo(b); });

    for (String word : dictionary) {        if (isSubsequence(s, word)) {            return word;        }    }     return "";} // Helper function to check if word is a subsequence of sprivate boolean isSubsequence(String s, String word) {    int i = 0; // pointer for s    int j = 0; // pointer for word    while (i < s.length() && j < word.length()) {        if (s.charAt(i) == word.charAt(j)) {            j++;        }        i++;    }    return j == word.length();}

}

Complexity

Time

O(m log m * l + m * n), where `m` is the number of words in the dictionary, `n` is the length of `s`, and `l` is the average length of words in the dictionary. The sorting step takes `O(m log m * l)` due to string comparisons. The iteration and subsequence check takes `O(m * n)` in the worst case. The sorting cost often dominates.

Space

O(log m) or O(m) for sorting. In Java, `Collections.sort` for lists uses Timsort which has an auxiliary space complexity of `O(log m)` on average and `O(m)` in the worst case.

Trade-offs

Pros

  • The logic after sorting is very clean and simple: find the first match and return.

  • Reduces complex conditional checks inside the loop.

Cons

  • The initial sorting step can be computationally expensive, especially for a large dictionary.

  • The overall time complexity is generally worse than the linear scan approach.

Solutions

class Solution {public  String findLongestWord(String s, List<String> dictionary) {    String ans = "";    for (String a : dictionary) {      if (check(s, a) &&          (ans.length() < a.length() ||           (ans.length() == a.length() && a.compareTo(ans) < 0))) {        ans = a;      }    }    return ans;  }private  boolean check(String a, String b) {    int m = a.length(), n = b.length();    int i = 0, j = 0;    while (i < m && j < n) {      if (a.charAt(i) == b.charAt(j)) {        ++j;      }      ++i;    }    return j == n;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem