Longest Word in Dictionary through Deleting

medium two pointers string

Problem

Given s and a dictionary of words, return the longest word in the dictionary that can be formed by deleting some characters of s. Break ties by lexicographic order; return "" if none qualifies.

Inputs = "abpcplea", words = ["ale","apple","monkey","plea"]

Output"apple"

Both "apple" and "plea" fit; "apple" wins on length, "plea" on lex order — length wins first.

words (comma-separated)

def find_longest_word(s, dictionary):
    best = ""
    for w in dictionary:
        i = 0
        for ch in s:
            if i < len(w) and w[i] == ch:
                i += 1
        if i == len(w):
            if len(w) > len(best) or (len(w) == len(best) and w < best):
                best = w
    return best

function findLongestWord(s, dictionary) {
  let best = "";
  for (const w of dictionary) {
    let i = 0;
    for (const ch of s) {
      if (i < w.length && w[i] === ch) i++;
    }
    if (i === w.length) {
      if (w.length > best.length || (w.length === best.length && w < best)) {
        best = w;
      }
    }
  }
  return best;
}

class Solution {
    public String findLongestWord(String s, List<String> dictionary) {
        String best = "";
        for (String w : dictionary) {
            int i = 0;
            for (int k = 0; k < s.length() && i < w.length(); k++) {
                if (s.charAt(k) == w.charAt(i)) i++;
            }
            if (i == w.length()) {
                if (w.length() > best.length()
                    || (w.length() == best.length() && w.compareTo(best) < 0)) {
                    best = w;
                }
            }
        }
        return best;
    }
}

string findLongestWord(string s, vector<string>& dictionary) {
    string best = "";
    for (auto& w : dictionary) {
        int i = 0;
        for (char ch : s) if (i < (int)w.size() && w[i] == ch) i++;
        if (i == (int)w.size()) {
            if ((int)w.size() > (int)best.size() ||
               ((int)w.size() == (int)best.size() && w < best))
                best = w;
        }
    }
    return best;
}

Explanation

"Formed by deleting characters of s" is just a fancy way of saying the word must be a subsequence of s — its letters appear inside s in order. So we test each dictionary word with a quick two-pointer subsequence check and remember the best one.

For a candidate w, keep a pointer i into w and walk through every character of s. Each time s's character equals w[i], advance i. If i reaches len(w), then all of w was found in order, so w fits.

Among the words that fit, we want the longest, and on a tie we want the lexicographically smallest. That is exactly the condition len(w) > len(best) or (len(w) == len(best) and w < best), which updates best when a better word appears.

Example: s = "abpcplea" with words ["ale","apple","monkey","plea"]. Both "apple" and "plea" are subsequences, but "apple" is longer (5 vs 4), so it wins and the answer is "apple".

If no word fits, best stays as the empty string "", which is returned.

Time: O(|s| · Σ|wᵢ|) Space: O(1)