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 shortestcompleting word in _words . It is guaranteed an answer exists. If there are multiple shortest completing words, return the first one that occurs in words.

Examples

Example 1

1
2
3
4
5
6
7
8

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

1
2
3

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.

Solution

Method 1 – Hash Counting

Intuition

We need to check for each word if it contains all the required letters (with counts) from the license plate. By counting the frequency of each letter in the license plate and each word, we can efficiently check if a word is a completing word.

Approach

  1. Count the frequency of each letter (case-insensitive) in the license plate, ignoring digits and spaces.
  2. For each word in the list:
    • Count the frequency of each letter in the word.
    • Check if the word contains at least as many of each required letter as in the license plate.
    • If so, and the word is shorter than the current answer, update the answer.
  3. Return the first shortest completing word found.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
public:
    string shortestCompletingWord(string licensePlate, vector<string>& words) {
        vector<int> cnt(26);
        for (char c : licensePlate) {
            if (isalpha(c)) cnt[tolower(c) - 'a']++;
        }
        string ans;
        for (const string& w : words) {
            vector<int> wc(26);
            for (char c : w) wc[c - 'a']++;
            bool ok = true;
            for (int i = 0; i < 26; ++i) {
                if (cnt[i] > wc[i]) { ok = false; break; }
            }
            if (ok && (ans.empty() || w.size() < ans.size())) ans = w;
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

func shortestCompletingWord(licensePlate string, words []string) string {
    cnt := [26]int{}
    for _, c := range licensePlate {
        if c >= 'A' && c <= 'Z' {
            cnt[c-'A']++
        } else if c >= 'a' && c <= 'z' {
            cnt[c-'a']++
        }
    }
    ans := ""
    for _, w := range words {
        wc := [26]int{}
        for _, c := range w {
            wc[c-'a']++
        }
        ok := true
        for i := 0; i < 26; i++ {
            if cnt[i] > wc[i] {
                ok = false
                break
            }
        }
        if ok && (ans == "" || len(w) < len(ans)) {
            ans = w
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    public String shortestCompletingWord(String licensePlate, String[] words) {
        int[] cnt = new int[26];
        for (char c : licensePlate.toCharArray()) {
            if (Character.isLetter(c)) cnt[Character.toLowerCase(c) - 'a']++;
        }
        String ans = null;
        for (String w : words) {
            int[] wc = new int[26];
            for (char c : w.toCharArray()) wc[c - 'a']++;
            boolean ok = true;
            for (int i = 0; i < 26; ++i) {
                if (cnt[i] > wc[i]) { ok = false; break; }
            }
            if (ok && (ans == null || w.length() < ans.length())) ans = w;
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    fun shortestCompletingWord(licensePlate: String, words: Array<String>): String {
        val cnt = IntArray(26)
        for (c in licensePlate) {
            if (c.isLetter()) cnt[c.lowercaseChar() - 'a']++
        }
        var ans: String? = null
        for (w in words) {
            val wc = IntArray(26)
            for (c in w) wc[c - 'a']++
            var ok = true
            for (i in 0 until 26) {
                if (cnt[i] > wc[i]) { ok = false; break }
            }
            if (ok && (ans == null || w.length < ans.length)) ans = w
        }
        return ans!!
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution:
    def shortestCompletingWord(self, licensePlate: str, words: list[str]) -> str:
        cnt = [0] * 26
        for c in licensePlate:
            if c.isalpha():
                cnt[ord(c.lower()) - ord('a')] += 1
        ans = ''
        for w in words:
            wc = [0] * 26
            for c in w:
                wc[ord(c) - ord('a')] += 1
            if all(cnt[i] <= wc[i] for i in range(26)):
                if not ans or len(w) < len(ans):
                    ans = w
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

impl Solution {
    pub fn shortest_completing_word(license_plate: String, words: Vec<String>) -> String {
        let mut cnt = [0; 26];
        for c in license_plate.chars() {
            if c.is_ascii_alphabetic() {
                cnt[c.to_ascii_lowercase() as usize - 'a' as usize] += 1;
            }
        }
        let mut ans = String::new();
        for w in &words {
            let mut wc = [0; 26];
            for c in w.chars() {
                wc[c as usize - 'a' as usize] += 1;
            }
            if (0..26).all(|i| cnt[i] <= wc[i]) {
                if ans.is_empty() || w.len() < ans.len() {
                    ans = w.clone();
                }
            }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    shortestCompletingWord(licensePlate: string, words: string[]): string {
        const cnt = Array(26).fill(0);
        for (const c of licensePlate) {
            if (/[a-zA-Z]/.test(c)) cnt[c.toLowerCase().charCodeAt(0) - 97]++;
        }
        let ans = '';
        for (const w of words) {
            const wc = Array(26).fill(0);
            for (const c of w) wc[c.charCodeAt(0) - 97]++;
            let ok = true;
            for (let i = 0; i < 26; ++i) {
                if (cnt[i] > wc[i]) { ok = false; break; }
            }
            if (ok && (ans === '' || w.length < ans.length)) ans = w;
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(L + W * S), where L = length of licensePlate, W = number of words, S = average word length. We count letters for licensePlate and for each word.
  • 🧺 Space complexity: O(1) for the counters (since alphabet size is constant), plus O(W * S) for input storage.