# Shortest Completing Word
**Difficulty:** EASY
[External](https://leetcode.com/problems/shortest-completing-word)
Canonical: https://scaleengineer.com/dsa/problems/shortest-completing-word
**Data structures:** Array, Hash Table, String
---
## Problem
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`.

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

**Constraints:**

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

# Approaches
## Brute-Force with List Manipulation
This approach directly simulates the process of checking for character presence. First, we create a list of all required characters from the `licensePlate`. Then, for each word in the input array, we create a copy of this character list. We iterate through the word's characters, and for each character, we try to remove it from our copied list. If a word successfully empties the list, it means it contains all the required characters. We keep track of the first such word that has the minimum length.
**Time:** `O(L + N * M * L)` where `L` is the length of `licensePlate`, `N` is the number of words, and `M` is the maximum length of a word. The `O(M * L)` term comes from iterating `M` times (for each character in a word) and performing a list removal which takes `O(L)` time. · **Space:** `O(L)` to store the list of required characters from the `licensePlate` and its temporary copy for each word.
**Pros:** The logic is a direct translation of the problem's requirements, making it easy to conceptualize.
**Cons:** Inefficient due to the `list.remove(Object)` operation inside a loop, which has a linear time complexity with respect to the list size.; Creates a new list object for every word, which can be memory-intensive for a large number of words.
### Explanation
In this method, we first parse the `licensePlate` to build a list of the letters it contains, ignoring case, numbers, and spaces. For instance, `"1s3 PSt"` would result in a list `['s', 'p', 's', 't']`. Then, we iterate through every `word` from the `words` array. For each `word`, we make a copy of our required characters list. We then iterate through the `word`'s characters, removing them from the copied list one by one. If the list becomes empty, it signifies that the `word` contains all necessary letters. We then compare its length with the shortest completing word found so far and update if necessary. The first word encountered with the minimum length is our answer.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    public String shortestCompletingWord(String licensePlate, String[] words) {
        List<Character> requiredChars = new ArrayList<>();
        for (char c : licensePlate.toLowerCase().toCharArray()) {
            if (Character.isLetter(c)) {
                requiredChars.add(c);
            }
        }

        String shortestWord = null;

        for (String word : words) {
            List<Character> tempChars = new ArrayList<>(requiredChars);
            for (char c : word.toCharArray()) {
                // Note: remove(Object) is needed to remove the element,
                // not remove(int index) which would treat char as an index.
                tempChars.remove(Character.valueOf(c));
            }

            if (tempChars.isEmpty()) {
                if (shortestWord == null || word.length() < shortestWord.length()) {
                    shortestWord = word;
                }
            }
        }
        return shortestWord;
    }
}
```
### Algorithm
- Initialize an empty `List<Character>` called `requiredChars`.
- Iterate through the `licensePlate`. For each character, if it's a letter, convert it to lowercase and add it to `requiredChars`.
- Initialize a `String` variable `result` to `null`.
- Iterate through each `word` in the `words` array.
- Create a temporary list `tempChars` as a copy of `requiredChars`.
- Iterate through the characters of the current `word`. For each character `c`, attempt to remove its first occurrence from `tempChars`.
- After iterating through the `word`, check if `tempChars` is empty.
- If `tempChars` is empty, the current `word` is a completing word. Check if `result` is `null` or if the current `word` is shorter than `result`. If so, update `result` to the current `word`.
- After checking all words, return `result`.

## Optimized Approach using Frequency Arrays
A more efficient method is to use frequency counting. Instead of repeatedly searching and removing characters, we can pre-calculate the frequency of required characters from the `licensePlate`. We store these counts in an array of size 26 (for each letter 'a' through 'z'). Then, for each word in the `words` array, we also calculate its character frequency. A word is "completing" if its character counts are greater than or equal to the required counts for all letters. This avoids costly list operations and provides a much faster solution.
**Time:** `O(L + N * M)` where `L` is the length of `licensePlate`, `N` is the number of words, and `M` is the maximum length of a word. We spend `O(L)` to process the license plate and `O(M)` for each of the `N` words. The comparison of frequency arrays takes constant time, `O(26)`. · **Space:** `O(1)` because the space used for the frequency arrays is constant (size 26), regardless of the input size.
**Pros:** Highly efficient in both time and space, representing the optimal solution.; Uses a standard and effective pattern for frequency-based string problems.; The fixed-size array is faster and more memory-efficient than a HashMap for this specific problem.
**Cons:** Slightly more abstract than the direct simulation, but the logic is standard for this type of problem.
### Explanation
This optimized approach hinges on character frequency analysis. First, we create a character frequency map for the `licensePlate`. Since we only care about lowercase English letters, a simple integer array of size 26 is perfect for this. We iterate through the `licensePlate`, count the occurrences of each letter, and store them in this array. 

Next, we iterate through each `word` in the `words` array. For each `word`, we generate its own frequency array. Then, we compare the word's frequency array with the license plate's frequency array. If for every letter of the alphabet, the count in the word's array is greater than or equal to the count in the license plate's array, the word is a 'completing word'. We keep track of the shortest such word found, ensuring we pick the first one in case of a tie in length.

```java
class Solution {
    public String shortestCompletingWord(String licensePlate, String[] words) {
        int[] plateCounts = new int[26];
        for (char c : licensePlate.toCharArray()) {
            if (Character.isLetter(c)) {
                plateCounts[Character.toLowerCase(c) - 'a']++;
            }
        }

        String result = null;

        for (String word : words) {
            int[] wordCounts = new int[26];
            for (char c : word.toCharArray()) {
                wordCounts[c - 'a']++;
            }

            boolean isCompleting = true;
            for (int i = 0; i < 26; i++) {
                if (wordCounts[i] < plateCounts[i]) {
                    isCompleting = false;
                    break;
                }
            }

            if (isCompleting) {
                if (result == null || word.length() < result.length()) {
                    result = word;
                }
            }
        }
        return result;
    }
}
```
### Algorithm
- Create an integer array `plateCounts` of size 26, initialized to zeros.
- Iterate through the `licensePlate`. For each character, if it's a letter, convert it to lowercase and increment the corresponding count in `plateCounts`.
- Initialize a `String` variable `result` to `null`.
- Iterate through each `word` in the `words` array.
- Create a temporary integer array `wordCounts` of size 26 for the current word's character frequencies and populate it.
- Compare `wordCounts` with `plateCounts`. The word is completing if `wordCounts[i] >= plateCounts[i]` for all `i` from 0 to 25.
- If the word is completing, check if `result` is `null` or if the current `word` is shorter than `result`. If so, update `result` to the current `word`.
- After checking all words, return `result`.

# Solutions
### Java

```java
class Solution { public String shortestCompletingWord ( String licensePlate , String [] words ) { int [] cnt = new int [ 26 ]; for ( int i = 0 ; i < licensePlate . length (); ++ i ) { char c = licensePlate . charAt ( i ); if ( Character . isLetter ( c )) { cnt [ Character . toLowerCase ( c ) - 'a' ]++; } } String ans = "" ; for ( String w : words ) { if (! ans . isEmpty () && w . length () >= ans . length ()) { continue ; } int [] t = new int [ 26 ]; for ( int i = 0 ; i < w . length (); ++ i ) { t [ w . charAt ( i ) - 'a' ]++; } boolean ok = true ; for ( int i = 0 ; i < 26 ; ++ i ) { if ( t [ i ] < cnt [ i ]) { ok = false ; break ; } } if ( ok ) { ans = w ; } } return ans ; } }
```

### CPP

```cpp
class Solution {
public:
  string shortestCompletingWord(string licensePlate, vector<string> &words) {
    int cnt[26]{};
    for (char &c : licensePlate) {
      if (isalpha(c)) {
        ++cnt[tolower(c) - 'a'];
      }
    }
    string ans;
    for (auto &w : words) {
      if (ans.size() && ans.size() <= w.size()) {
        continue;
      }
      int t[26]{};
      for (char &c : w) {
        ++t[c - 'a'];
      }
      bool ok = true;
      for (int i = 0; i < 26; ++i) {
        if (cnt[i] > t[i]) {
          ok = false;
          break;
        }
      }
      if (ok) {
        ans = w;
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def shortestCompletingWord(self, licensePlate: str, words: List[str]) -> str: cnt = Counter(c . lower() for c in licensePlate if c . isalpha()) ans = None for w in words: if ans and len(w) >= len(ans): continue t = Counter(w) if all(v <= t[c] for c, v in cnt . items()): ans = w return ans

```