Shortest Completing Word

easy string hash map counting

Problem

Given a licence plate string and an array of words, return the shortest word that contains all letters (ignoring case and digits) of the plate. Ties go to the earliest such word.

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

Output"steps"

Both "step" and "steps" cover the letters, but step is missing an extra s; steps wins as shortest.

plate ; words (comma-separated)

def shortestCompletingWord(licensePlate, words):
    from collections import Counter
    need = Counter(c.lower() for c in licensePlate if c.isalpha())
    best = None
    for w in words:
        wc = Counter(w)
        if all(wc[c] >= n for c, n in need.items()):
            if best is None or len(w) < len(best): best = w
    return best

function shortestCompletingWord(plate, words) {
  const need = {};
  for (const c of plate.toLowerCase()) if (c >= 'a' && c <= 'z') need[c] = (need[c] || 0) + 1;
  let best = null;
  for (const w of words) {
    const have = {};
    for (const c of w) have[c] = (have[c] || 0) + 1;
    let ok = true;
    for (const c in need) if ((have[c] || 0) < need[c]) { ok = false; break; }
    if (ok && (best === null || w.length < best.length)) best = w;
  }
  return best;
}

class Solution {
  public String shortestCompletingWord(String plate, String[] words) {
    int[] need = new int[26];
    for (char c : plate.toLowerCase().toCharArray()) if (c >= 'a' && c <= 'z') need[c - 'a']++;
    String best = null;
    for (String w : words) {
      int[] have = new int[26];
      for (char c : w.toCharArray()) have[c - 'a']++;
      boolean ok = true;
      for (int i = 0; i < 26; i++) if (have[i] < need[i]) { ok = false; break; }
      if (ok && (best == null || w.length() < best.length())) best = w;
    }
    return best;
  }
}

class Solution {
public:
  string shortestCompletingWord(string plate, vector<string>& words) {
    int need[26] = {0};
    for (char c : plate) if (isalpha(c)) need[tolower(c) - 'a']++;
    string best;
    for (auto& w : words) {
      int have[26] = {0};
      for (char c : w) have[c - 'a']++;
      bool ok = true;
      for (int i = 0; i < 26; i++) if (have[i] < need[i]) { ok = false; break; }
      if (ok && (best.empty() || w.size() < best.size())) best = w;
    }
    return best;
  }
};

Explanation

We need a word that contains every required letter, the right number of times. The trick is to first count what the plate demands, then check each candidate word against that count and keep the shortest one that passes.

From the licence plate we build need, a count of each letter (lowercased, ignoring digits and spaces). For the example plate "1s3 PSt", that is s: 2, p: 1, t: 1.

For each word we count its own letters into wc, then verify wc[c] >= n for every required letter and count n. A word qualifies only if it has at least as many of each needed letter, so duplicates matter.

Among all qualifying words we track best, replacing it whenever we find a shorter winner. Because we scan in order and only swap on a strictly shorter length, ties naturally keep the earliest word.

Example: words ["step", "steps", "stripe", "stepple"]. "step" has only one s but we need two, so it fails. "steps" has two s, one p, one t and is the shortest that qualifies, so the answer is "steps".

Time: O(N * L) Space: O(1)