# Longest Word in Dictionary through Deleting
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/longest-word-in-dictionary-through-deleting)
Canonical: https://scaleengineer.com/dsa/problems/longest-word-in-dictionary-through-deleting
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array, String
---
## 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 <= 1000`
* `1 <= dictionary.length <= 1000`
* `1 <= dictionary[i].length <= 1000`
* `s` and `dictionary[i]` consist of lowercase English letters.

# Approaches
## Sorting the Dictionary First
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.
**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.
**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.
### Explanation
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 s
    private 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();
    }
}
```
### 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.

## Linear Scan without Sorting
This approach iterates through the dictionary without any pre-sorting. It maintains a variable, say `longestWord`, to keep track of the best candidate found so far. For each word in the dictionary, it first checks if it can be formed by deleting characters from `s` (i.e., if it's a subsequence). If it is, it then compares this word with `longestWord` based on the problem's criteria (length and lexicographical order) and updates `longestWord` if the current word is a better candidate.
**Time:** O(m * n), where `m` is the number of words in the dictionary and `n` is the length of `s`. For each of the `m` words, we perform a subsequence check which takes `O(n)` time. · **Space:** O(l_max), where `l_max` is the length of the longest word in the dictionary, used to store the result string. The auxiliary space complexity is O(1).
**Pros:** More efficient than the sorting approach as it avoids the expensive `O(m log m * l)` sorting step.; Simple to implement and understand.
**Cons:** Requires explicit comparison logic inside the loop to handle tie-breaking rules.
### Explanation
This approach avoids the overhead of sorting by iterating through the dictionary once and keeping track of the best answer found so far. A variable `longestWord` is used to store the best result encountered during the scan. For each word, we check if it's a subsequence of `s`. If it is, we then check if it's a better answer than our current `longestWord` based on length and lexicographical order. ```java
import java.util.List;

class Solution {
    public String findLongestWord(String s, List<String> dictionary) {
        String longestWord = "";
        for (String word : dictionary) {
            if (isSubsequence(s, word)) {
                // Check if the current word is a better answer
                if (word.length() > longestWord.length() ||
                   (word.length() == longestWord.length() && word.compareTo(longestWord) < 0)) {
                    longestWord = word;
                }
            }
        }
        return longestWord;
    }

    // Helper function to check if word is a subsequence of s
    private 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();
    }
}
```
### Algorithm
- Initialize an empty string `longestWord = ""`. - Iterate through each `word` in the `dictionary`. - For each `word`, 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. - If `word` is a subsequence of `s`, compare it with the current `longestWord`: -   If `word.length()` > `longestWord.length()`, update `longestWord = word`. -   If `word.length()` == `longestWord.length()` and `word` is lexicographically smaller than `longestWord`, update `longestWord = word`. - After iterating through all words, return `longestWord`.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
class Solution {
public:
  string findLongestWord(string s, vector<string> &dictionary) {
    string ans = "";
    for (string &a : dictionary)
      if (check(s, a) &&
          (ans.size() < a.size() || (ans.size() == a.size() && a < ans)))
        ans = a;
    return ans;
  }
  bool check(string &a, string &b) {
    int m = a.size(), n = b.size();
    int i = 0, j = 0;
    while (i < m && j < n) {
      if (a[i] == b[j])
        ++j;
      ++i;
    }
    return j == n;
  }
};

```

### Python

```python
class Solution:
    def findLongestWord(self, s: str, dictionary: List[str]) -> str: def check(a, b): m, n = len(a), len(b) i = j = 0 while i < m and j < n: if a[i] == b[j]: j += 1 i += 1 return j == n ans = '' for a in dictionary: if check(s, a) and (len(ans) < len(a) or (len(ans) == len(a) and ans > a)): ans = a return ans

```