Shortest Completing Word Leetcode Solution

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

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 Solution

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

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"]
"pest"

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”.

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.

Code

C++ code for Shortest Completing Word Leetcode Solution

#include<bits/stdc++.h>
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'))
            m[tolower(x)]++;
    }
    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'))
                mm[tolower(x)]++;
        }
        bool cant = false;
        for(char i='a';i<='z';i++)
            if(mm[i] < m[i])
                cant = true;
        if(!cant){
            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);
}

steps

Java code for Shortest Completing Word Leetcode Solution

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

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));
  }
}
steps

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.

Space Complexity

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

Translate »