algoadvance

Leetcode 748. Shortest Completing Word

Problem Statement

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 the licensePlate (case insensitive). The letters in the licensePlate can be both uppercase and lowercase letters. Ignore numbers and spaces in the licensePlate. Return the shortest completing word in words. If there are multiple shortest completing words, return the first one that appears in words.

Clarifying Questions

  1. Can the licensePlate contain special characters?
    • Generally, it contains only alphanumeric characters, but for this problem, we only need to consider ignoring digits and spaces.
  2. Is the length of each word in the words array constrained?
    • Typically, the length will be reasonably constrained as per usual interview problem constraints.
  3. Are there constraints about the size of the licensePlate and the array words?
    • We can assume that both the licensePlate and the words array will be within a range suitable for typical coding interview problems.

Strategy

To solve this problem, we can follow these steps:

  1. Extract the character counts from licensePlate, ignoring non-letter characters.
  2. For each word in words, check if it can be a completing word.
  3. Track the shortest completing word by comparing lengths.

Code

#include <string>
#include <vector>
#include <cctype>
#include <unordered_map>
#include <algorithm>

using namespace std;

string shortestCompletingWord(string licensePlate, vector<string>& words) {
    unordered_map<char, int> charCount;

    // Helper lambda function to convert character to lowercase and check if it's a letter
    auto adjustAndCount = [&](char ch) {
        if (isalpha(ch)) {
            charCount[tolower(ch)]++;
        }
    };

    // Count frequencies of each letter in the licensePlate
    for (char ch : licensePlate) {
        adjustAndCount(ch);
    }

    string result;
    size_t minLen = numeric_limits<size_t>::max();

    for (const string& word : words) {
        unordered_map<char, int> wordCount;

        for (char ch : word) {
            wordCount[tolower(ch)]++;
        }

        bool isCompleting = true;

        for (const auto& pair : charCount) {
            if (wordCount[pair.first] < pair.second) {
                isCompleting = false;
                break;
            }
        }

        if (isCompleting && word.length() < minLen) {
            result = word;
            minLen = word.length();
        }
    }

    return result;
}

int main() {
    string licensePlate = "1s3 PSt";
    vector<string> words = {"step", "steps", "stripe", "stepple"};
    string result = shortestCompletingWord(licensePlate, words);
    cout << "Shortest completing word: " << result << endl;
    return 0;
}

Time Complexity

The time complexity analysis for this solution involves:

  1. Processing License Plate Characters: O(n), where n is the length of the licensePlate.
  2. Iterating through Words: O(m * k), where m is the number of words and k is the maximum length of a word.

Overall, the time complexity is O(n + m * k), which is efficient for typical constraints expected in interviews.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI