Given a string licensePlate and an array of strings words, find the shortest completing word in words.

A completing word is a word that contains all the letters in licensePlate. Ignore numbers and spaces in licensePlate, and treat letters as case insensitive. If a letter appears more than once in licensePlate, then it must appear in the word the same number of times or more.

For example, if licensePlate = "aBc 12c", then it contains letters 'a', 'b' (ignoring case), and 'c' twice. Possible completing words are "abccdef", "caaacab", and "cbca".

Return the shortest completing word in words. It is guaranteed an answer exists. If there are multiple shortest completing words, return the first one that occurs in words.

&nbsp;
Example 1:

Input: licensePlate = "1s3 PSt", words = ["step","steps","stripe","stepple"]
Output: "steps"
Explanation: licensePlate contains letters 's', 'p', 's' (ignoring case), and 't'.
"step" contains 't' and 'p', but only contains 1 's'.
"steps" contains 't', 'p', and both 's' characters.
"stripe" is missing an 's'.
"stepple" is missing an 's'.
Since "steps" is the only word containing all the letters, that is the answer.


Example 2:

Input: licensePlate = "1s3 456", words = ["looks","pest","stew","show"]
Output: "pest"
Explanation: licensePlate only contains the letter 's'. All the words contain 's', but among these "pest", "stew", and "show" are shortest. The answer is "pest" because it is the word that appears earliest of the 3.


&nbsp;
Constraints:


	1 &lt;= licensePlate.length &lt;= 7
	licensePlate contains digits, letters (uppercase or lowercase), or space ' '.
	1 &lt;= words.length &lt;= 1000
	1 &lt;= words[i].length &lt;= 15
	words[i] consists of lower case English letters.


class Solution:
    def shortestCompletingWord(self, licensePlate: str, words: List[str]) -> str:
        newPlate = ''         # modify the licensePlate
        for i in licensePlate:
            if i.isalpha():
                newPlate += i.lower()
                
        c = Counter(newPlate)
        l1 = []         # store (word,len,index)
        for idx,word in enumerate(words):
            if Counter(word) >= c:
                l1.append((word,len(word),idx))
        l1.sort(key = lambda x:(x[1],idx))
        return l1[0][0]
class Solution {
    public String shortestCompletingWord(String licensePlate, String[] words) {
        //Store count of letters in LicensePlate
        int[] licensePlateCount = new int[26];
        
        //To store all words which meet the criteria
        ArrayList<String> res = new ArrayList<>();
        //To find min length word that meets the criteria
        int min = Integer.MAX_VALUE;
        
        //Add char count for each char in LicensePlate
        for(Character c:licensePlate.toCharArray()) {
            if(isChar(c)) {
                licensePlateCount[Character.toLowerCase(c) - 'a']++;
            }
        }
        
        //Add char count for each word in words
        for(String word : words) {
            int[] wordCharCount = new int[26];
            boolean flag = true;
            
            for(Character c:word.toCharArray()) {
                wordCharCount[Character.toLowerCase(c) - 'a']++;
            }
            
            //Eliminate words that don't satisfy the criteria
            for(int i = 0; i<26;i++) {
                if(licensePlateCount[i] > wordCharCount[i]) flag = false;
            }
            
            //Add words satisfying criteria to res and calculate min word length
            if(flag) {
                res.add(word);
                if(word.length() < min) min = word.length();
            }
        }
        
        //Return 1st word in array meeting all criteria
        for(int i = 0; i < res.size();i++) {
            if(res.get(i).length() == min) return res.get(i);
        }
        
        //If not found, return -1 (or whatever interviewer expects)
        return "-1";
    }
    
    private boolean isChar(Character c) {
        if((c >='a' && c <='z') ||
           (c>='A' && c<='Z')) return true;
        
        return false;
    }
}
	class Solution {
public:
    string shortestCompletingWord(string licensePlate, vector<string>& words) 
    {
        string ans="";
        vector<int> m(26,0);
        for(auto &lp:licensePlate)
        {
            if(isalpha(lp))
                m[tolower(lp)-'a']++;
        }
        for(auto &word:words)
        {
            vector<int> v=m;
            for(auto &ch:word)
            {
                v[tolower(ch)-'a']--;
            }
            bool flag=true;
            for(int i=0;i<26;i++)
            {
                if(v[i]>0)
                    flag =false;
            }
            if(flag&&(ans==""||ans.size()>word.size()))
                ans=word;
        }
        return ans;
        
    }
};
//if you like the solution plz upvote.
var shortestCompletingWord = function(licensePlate, words) {

    // Object to hold the shortest word that matches
    var match = {'found':false, 'word':''};

    // Char array to hold the upper case characters we want to match
    var licensePlateChars = licensePlate.toUpperCase().replace(/[^A-Z]/g, '').split('');

    words.forEach(function (word) {
        // if we already have a match make sure that the word we are checking is shorter
        if (!match.found || word.length < match.word.length) {
            var replaceWord = word.toUpperCase();

            // Loop over each character in the license plate and replace one at a time
            // the key here is that replace will only replace 1 S even if there are 2
            licensePlateChars.forEach(function (lChar) {
                replaceWord = replaceWord.replace(lChar, '');
            });

            // We know the word works if the length of the word minus
            // the length of chars equals the length of the new word
            if (word.length - licensePlateChars.length === replaceWord.length) {
                match.found = true;
                match.word = word
            }
        }
    });

    return match.word;
};
Shortest Completing Word