Shortest Completing Word Leetcode Solution  

Difficulty Level Easy
Frequently asked in Google
algorithms coding HashMap Interview interviewprep LeetCode LeetCodeSolutions

The problem Shortest Completing Word Leetcode Solution states that you are given a license plate and an array of os strings. You need to find the shortest completing word. A competing word is defined as a word that has all the alphabets in the license plate (case insensitive). The frequency of letters in completing word can be greater than the frequency of letters in the license plate but it can not be less. So, you need to find the shortest completing word among the array of strings. So, let’s take a look at a few examples.

Shortest Completing Word Leetcode SolutionPin

licensePlate = "1s3 PSt", words = ["step","steps","stripe","stepple"]

Explanation: The word given in the license plate has 2 s and 1 t. The word from the array is “step” which has only a single one. Thus “step” is not a completing word. But, “steps” has  2 s, 1 t, and other letters. The word “steps” satisfies the condition to be a completing word. And it is also the shortest completing word. Thus, it is returned as an answer.

licensePlate = "1s3 456", words = ["looks","pest","stew","show"]

Explanation: All the words from the array are completing words. But the last 3 words are the shortest completing words. Among the shortest completing words, we return the first shortest completing word that is “pest”.

Table of Contents

Please click Like if you loved this article?

Approach for Shortest Completing Word Leetcode Solution  

The problem Shortest Completing Word Leetcode Solution asked us to find the shortest completing word. We have already specified what a completing word is, in the description of the problem statement. So, to find the shortest completing word. First, we have to find the frequency of the letters on the license plate. This frequency is insensitive of the case of the letter. Then we traverse over the array of strings. And once again we perform the same operation of finding the frequency of letters. Then we check if the current word is a completing word. If it is and the size of the current word is smaller than the previous completing word, we update the answer. In the end, we return the shortest completing word.


C++ code for Shortest Completing Word Leetcode Solution

using namespace std;

string shortestCompletingWord(string licensePlate, vector<string>& words) {
    unordered_map<char, int> m;
    for(auto x: licensePlate){
        if((x>='A' && x<='Z') || (x>='a' && x<='z'))
    string answer = string(16, 'a');
    for(auto word: words){
        unordered_map<char, int> mm;
        for(auto x: word){
            if((x>='A' && x<='Z') || (x>='a' && x<='z'))
        bool cant = false;
        for(char i='a';i<='z';i++)
            if(mm[i] < m[i])
                cant = true;
            if(word.length() < answer.length())
                answer = word;
    return answer;

int main(){
    string licensePlate = "1s3 PSt";
    vector<string> words({"step","steps","stripe","stepple"});
    cout<<shortestCompletingWord(licensePlate, words);

Java code for Shortest Completing Word Leetcode Solution

import java.util.*;
import java.lang.*;

class Main
  public static String shortestCompletingWord(String licensePlate, String[] words) {
       HashMap <Character, Integer> m = new HashMap<Character, Integer>();
        int licensePlateSize = licensePlate.length();
        for(int i=0;i<licensePlateSize;i++){
            char x = licensePlate.charAt(i);
            if((x>='A' && x<='Z') || (x>='a' && x<='z'))
                m.put(Character.toLowerCase(x), m.containsKey(Character.toLowerCase(x)) ? (m.get(Character.toLowerCase(x)) + 1) : 1);
        String answer = "aaaaaaaaaaaaaaaa";
        for(String word: words){
            HashMap<Character, Integer> mm = new HashMap<Character, Integer>();
            int wordSize = word.length();
            for(int i=0;i<wordSize;i++){
                char x = word.charAt(i);
                if((x>='A' && x<='Z') || (x>='a' && x<='z'))
                    mm.put(Character.toLowerCase(x), mm.containsKey(Character.toLowerCase(x)) ? (mm.get(Character.toLowerCase(x)) + 1) : 1);
            boolean cant = false;
            for(char i='a';i<='z';i++){
                int a = m.containsKey(i) ? m.get(i) : 0;
                int b = mm.containsKey(i) ? mm.get(i) : 0;
                if(b < a)
                    cant = true;
            if(cant == false){
                if(word.length() < answer.length())
                    answer = word;
        return answer; 
  public static void main (String[] args) throws java.lang.Exception{
    String licensePlate = "1s3 PSt";
      String words[] = {"step","steps","stripe","stepple"};
      System.out.print(shortestCompletingWord(licensePlate, words));

Complexity Analysis  

Time Complexity

O(N), where N is the number of words in the array of strings. Thus the entire algorithm has linear time complexity.

See also
Count Subarrays with Same Even and Odd Elements

Space Complexity

O(1), since we use two HashMaps of constant size. The space complexity for the entire algorithm is constant.

Please click Like if you loved this article?

Ads Blocker Image Powered by Code Help Pro
Ads Blocker Detected!!!

This website does not work properly with AdBlock. We have detected that you are using extensions to block ads. Please disable Adblocker to view the content.