# Shortest Completing Word Leetcode Solution

Difficulty Level Easy
algorithms coding HashMap Interview interviewprep LeetCode LeetCodeSolutionsViews 743

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. `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;
if((x>='A' && x<='Z') || (x>='a' && x<='z'))
m[tolower(x)]++;
}
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){
}
}
}

int main(){
vector<string> words({"step","steps","stripe","stepple"});
}
```
`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>();
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);
}
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){
}
}
}

public static void main (String[] args) throws java.lang.Exception{
String words[] = {"step","steps","stripe","stepple"};
}
}```
`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 »