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.

&nbsp;
Example 1:

Input: s = "abpcplea", dictionary = ["ale","apple","monkey","plea"]
Output: "apple"


Example 2:

Input: s = "abpcplea", dictionary = ["a","b","c"]
Output: "a"


&nbsp;
Constraints:


	1 &lt;= s.length &lt;= 1000
	1 &lt;= dictionary.length &lt;= 1000
	1 &lt;= dictionary[i].length &lt;= 1000
	s and dictionary[i] consist of lowercase English letters.


class Solution:
    def findLongestWord(self, s: str, dictionary: list[str]) -> str:
        solution = ""
        for word in dictionary:
            j = 0
            for i in range(len(s)):
                if s[i] == word[j]:
                    j+=1
                if j == len(word):
                    solution = word if len(word) > len(solution) or len(word) == len(solution) and word < solution  else solution
                    break
        return solution
class Solution {
    public String findLongestWord(String s, List<String> dictionary) {
        
        int[] fre=new int[26];
       
        
        String ans="";
        int flag=0;
        int[] fff=new int[26];
         char[] ch = s.toCharArray();
        for(char c : ch)
            fre[c-'a']+=1;
        
        for(String s1 : dictionary)
        { 
             fff=fre.clone();
             int[] fre1=new int[26];
             char[] ch1 = s1.toCharArray();
            for(char c : ch1)
            {
               
                fre1[c-'a']+=1;
            }
            
            for(char c : ch1)
            {
                if(fre1[c-'a'] <= fff[c-'a'])
                { flag=0;
                  fff[c-'a']-=1; 
                 fre1[c-'a']-=1;
                }
                else
                {flag=1;
                  break;}                
            }
            if(flag==0)
            {
                if(ans != "")
                {
                  if(ans.length() <s1.length())
                  {
                      
                      ans=s1;
                  }else
                  {
                      if(ans.length() ==s1.length())
                      {
                          int f=0;
                         for(int m=0;m<ans.length();m++)
                         {
                             if(ans.charAt(m)>s1.charAt(m))
                             {
                                 f=1;
                                 break;
                             }
                                 
                         }
                          if(f==1)
                              ans=s1;
                      }
                  }
                }
                else
                    ans =s1;
            }
            else
            {
                flag=0;
            }
        }
        
        return ans;
        
    }
}
class Solution {
private:
    //checks whether the string word is a subsequence of s
    bool isSubSeq(string &s,string &word){
        int start=0;
        for(int i=0;i<s.size();i++){
            if(s[i]==word[start]){
                //every character of word occurs in s, therefore we return true
                if(++start==word.size()){
                    return true;
                }
            }
        }
        return false;
    }
public:
    string findLongestWord(string s, vector<string>& dictionary) {
        string ans="";
        for(string word:dictionary){
            if(word.size()>=ans.size() and isSubSeq(s,word)){
                if(word.size()>ans.size()){
                    ans=word;
                } else if(word.size()==ans.size() and word<ans){
                    ans=word;
                }
            }
        }
        return ans;
    }
};
/**
 * @param {string} s
 * @param {string[]} dictionary
 * @return {string}
 */
var findLongestWord = function(s, dictionary) {
    const getLen = (s1, s2) => {
        let i = 0, j = 0;
        while(i < s1.length && j < s2.length) {
            if(s1[i] == s2[j]) { i++, j++; }
            else i++;
        }
        if(j != s2.length) return 0;
        return s2.length;
    }
    let ans = '', ml = 0;
    for(let word of dictionary) {
        const len = getLen(s, word);
        if(len > ml) {
            ans = word;
            ml = len;
        }
        else if(len == ml && ans > word) {
            ans = word;
        }
    }
    return ans;
};
Longest Word in Dictionary through Deleting