Code Implementation

class Solution:
    def findLongestWord(self, s: str, dictionary: List[str]) -> str:
        def is_subsequence(word, s):
            it = iter(s)
            return all(char in it for char in word)
        
        result = ""
        for word in dictionary:
            if is_subsequence(word, s):
                if len(word) > len(result) or (len(word) == len(result) and word < result):
                    result = word
        return result
      

class Solution {
public:
    bool isSubsequence(const string& word, const string& s) {
        int i = 0, j = 0;
        while (i < word.size() && j < s.size()) {
            if (word[i] == s[j]) i++;
            j++;
        }
        return i == word.size();
    }
    string findLongestWord(string s, vector<string>& dictionary) {
        string result = "";
        for (const string& word : dictionary) {
            if (isSubsequence(word, s)) {
                if (word.size() > result.size() || 
                    (word.size() == result.size() && word < result)) {
                    result = word;
                }
            }
        }
        return result;
    }
};
      

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

var findLongestWord = function(s, dictionary) {
    function isSubsequence(word, s) {
        let i = 0, j = 0;
        while (i < word.length && j < s.length) {
            if (word[i] === s[j]) i++;
            j++;
        }
        return i === word.length;
    }
    let result = "";
    for (let word of dictionary) {
        if (isSubsequence(word, s)) {
            if (
                word.length > result.length ||
                (word.length === result.length && word < result)
            ) {
                result = word;
            }
        }
    }
    return result;
};
      

Problem Description

Given a string s and a list of strings dictionary, find the longest string in dictionary that can be formed by deleting some characters of s without reordering the remaining characters. If there are multiple possible results, return the one that is lexicographically smallest. If there is no possible result, return an empty string.

• You may not reorder the characters of s – only delete.
• Each word in dictionary can be used at most once.
• If more than one word is the same length, choose the one that comes first in dictionary order (i.e., alphabetical order).

Thought Process

At first glance, this problem seems to require checking, for every word in dictionary, whether it can be formed by deleting characters from s. The naive approach would be to try every possible combination of deletions, but that's extremely inefficient.

Instead, we can notice that the problem reduces to checking whether a word is a subsequence of s. If it is, then we can form that word by deleting the appropriate characters from s. So, for each word in the dictionary, we check if it's a subsequence of s. If it is, we compare its length and lexicographic order to track the best candidate.

The brute-force solution would check every possible way to delete characters, but with the subsequence insight, we can check each word efficiently in linear time relative to the length of s.

Solution Approach

• Step 1: Initialize a variable to keep track of the best (longest, lexicographically smallest) word found so far.
• Step 2: For each word in dictionary, check if it is a subsequence of s:
  • Use two pointers: one for the word and one for s.
  • Advance the pointer in s whenever there is a character match.
  • If you reach the end of the word, it is a subsequence.
• Step 3: If the word is a subsequence, check if it is longer than the current best, or if it is the same length but lexicographically smaller. If so, update the best word.
• Step 4: After checking all words, return the best word found, or an empty string if none are valid.

This approach is efficient because checking if a word is a subsequence can be done in O(N) time, where N is the length of s. By iterating through the dictionary once, we ensure we consider all candidates.

Example Walkthrough

Consider s = "abpcplea" and dictionary = ["ale","apple","monkey","plea"].

1. Check "ale":
   • 'a' matches s[0], 'l' matches s[3], 'e' matches s[5] – all in order. "ale" is a subsequence.
   • Best so far: "ale".
2. Check "apple":
   • 'a' matches s[0], 'p' matches s[3], next 'p' matches s[4], 'l' matches s[5], 'e' matches s[6].
   • "apple" is a subsequence and longer than "ale". Update best to "apple".
3. Check "monkey":
   • 'm' is not found in s. Not a subsequence.
4. Check "plea":
   • 'p' matches s[3], 'l' matches s[5], 'e' matches s[6], 'a' matches s[7].
   • "plea" is a subsequence, but length is 4, less than "apple".

The answer is "apple".

Time and Space Complexity

• Brute-force approach:
  • Would try every possible deletion, which is exponential in the length of s.
• Optimized approach:
  • For each word in dictionary (let's say D words, each of length up to L), we check if it's a subsequence of s (length N).
  • Each subsequence check is O(N), so total time is O(D*N).
  • Space complexity is O(1) extra (not counting input), as we only store the result string.

Summary

This problem is elegantly solved by recognizing that forming a word from s via deletions is the same as checking if it is a subsequence. By iterating through the dictionary and checking each word with a two-pointer technique, we efficiently find the longest, lexicographically smallest valid word. This approach leverages simple string traversal and comparison, making it both readable and performant.