Problem Explanation

You are given a string (s) and a list dictionary (d), your task is to find the longest string in the list that can be formed by deleting some characters in the string. If there are multiple longest strings possible, then return the one that is smallest in lexicographical order. If there is no possibility to form a string in dictionary from given string then return an empty string.

In a much simpler way, the problem is asking to form a string in the dictionary (d) from the given string (s) that is a subsequence of the string. The string should be the longest string and if there are multiple strings of the same length then return the smallest in lexicographical order.

For example, if you are given a string s= "abpcplea" and a dictionary d = ["ale","apple","monkey","plea"]. You can form string "apple" from the given string which is the longest string that is why the output is "apple".

Approach

The solution uses the method of checking if a given string is a subsequence of another string. For checking if string a is the subsequence of string b, iterate through the string b and check if the characters of string a match the characters of string b. If it does increment the index of string a.

For every word in the dictionary, check if it is a subsequence of the given string. If it is, then check if it's length is larger than the current answer (initialized as an empty string). If it is, update the answer. If the lengths are equal, check the lexicographical order of these two strings and update the answer if the word is smaller.

If the word isn't a subsequence or it's length is shorter then the current answer, do nothing and continue with the next word in the dictionary.

Python Solution

1
2python
3class Solution:
4    def findLongestWord(self, s: str, d: List[str]) -> str:
5        d.sort() # sorting dictionary to get smallest in lexicographical order
6        ans = ''
7        for word in d:
8            i = 0
9            # Check if word is subsequence of s
10            for ch in s:
11                if i < len(word) and ch == word[i]:
12                    i += 1
13            # Check if the current word is longest answer, if so update ans
14            if i == len(word) and len(word) > len(ans):
15                ans = word
16        return ans

C++ Solution

1
2cpp
3class Solution {
4public:
5    string findLongestWord(string s, vector<string>& d) {
6        string ans;
7        for (string word : d) {
8            int i = 0;
9            // Check if word is subsequence of s
10            for (char c : s) if (i < word.size() && word[i] == c) i++;
11            // Check if the current word is longest answer, if so update ans
12            if (i == word.size() && (ans.size() < word.size() || (ans.size() == word.size() && word < ans)))
13                ans = word;
14        }
15        return ans;
16    }
17};

Java Solution

1
2java
3class Solution {
4    public String findLongestWord(String s, List<String> d) {
5        String ans = "";
6        for (String word : d) {
7            int i = 0;
8            // Check if word is subsequence of s
9            for (char c : s.toCharArray()) if (i < word.length() && word.charAt(i) == c) i++;
10            // Check if the current word is longest answer, if so update ans
11            if (i == word.length() && (word.length() > ans.length() || (word.length() == ans.length() && word.compareTo(ans) < 0)))
12                ans = word;
13        }
14        return ans;
15    }
16}

Javascript Solution

1
2javascript
3var findLongestWord = function(s, d) {
4    let ans = '';
5    for (let word of d){
6        let i = 0;
7        // Check if word is subsequence of s
8        for(let ch of s){
9            if(i < word.length && ch == word[i]){
10                i++
11            }
12        }
13        // Check if the current word is longest answer, if so update ans
14        if(i == word.length && word.length >= ans.length){
15            if(word.length > ans.length || word < ans){
16                ans = word;
17            }
18        }
19    }
20    return ans;
21};

C# Solution

1
2csharp
3public class Solution {
4    public string FindLongestWord(string s, IList<string> d) {
5        string ans = "";
6        foreach (string word in d) {
7            int i = 0;
8            // Check if word is subsequence of s
9            foreach (char c in s) if (i < word.Length && c == word[i]) i++;
10            // Check if the current word is longest answer, if so update ans
11            if (i == word.Length && (word.Length > ans.Length || (word.Length == ans.Length && string.Compare(word, ans) < 0)))
12                ans = word;
13        }
14        return ans;
15    }
16}

In each of the solutions, we're using the same approach. We're iterating over every word in the dictionary and checking if that word is a subsequence of the given string. Then we are checking if the current word is longest or not. If it is, we update that word as our answer. If this continues, we get the longest possible string subsequence from the string in the dictionary that is lexicographically smallest.

We iteratively go through every word in the dictionary and compare the length of word and its lexicographic order with the current answer. If it may qualify as the next answer then only we check it is a subsequence of the given string or not.

The order in which we check conditions of length and lexicographic order matters as if we check lexicographic order first then it might replace an answer which is longer but larger lexicographically.

These solutions use Greedy algorithms to solve the problem. The time complexity is approximately O(n^2), where n is the length of string as we have to iterate over the whole string for each word in the dictionary but this can be optimized if we skip the words in the dictionary which are impossible to be an answer (like the ones that are shorter than the current longest string or larger lexicographically).

In terms of space complexity, we use constant amounts of space in each case i.e., O(1), thus they're quite efficient.

To sum it up, the essence of the solution to this problem is reducing the search space by using the conditions given in the problem (length and lexicographic order) and using the central idea to check the subsequence that we have used in our approach. This central idea can be applied to other similar problems such as finding the longest subsequence or subarray with any given condition.