algoadvance

Leetcode 748. Shortest Completing Word

Problem Statement

You are given a string licensePlate and an array of strings words. The licensePlate string consists of alphanumeric characters and spaces. The spaces and numbers in licensePlate are irrelevant, and only the letters are relevant. Find the shortest completing word in words. A completing word is one that contains all the letters in the licensePlate (case insensitive). If there are multiple shortest completing words, return the first one that appears in the array.

Clarifying Questions

  1. Are the completing words case-sensitive? No, completing words must consider letters case-insensitively.
  2. Are there any constraints on the length of licensePlate and words? Typically constraints will be provided, but for this problem, consider reasonable limits (e.g., up to 1000 words, each up to 1000 characters).
  3. How to handle non-alphabetic characters in licensePlate? Ignore non-alphabetic characters.

Strategy

  1. Extract Relevant Letters: Extract and count letters from licensePlate ignoring spaces and numbers. Convert all letters to lowercase.
  2. Count Letters in Each Word: For each word in words, create a count of its letters.
  3. Check Completing Words: Check each word to see if it contains all the required letters in the required frequency. Track the shortest word that meets this criterion.
  4. Efficiency: Use counts in hash maps to compare letter frequencies efficiently.

Code

import java.util.*;

public class Solution {
    public String shortestCompletingWord(String licensePlate, String[] words) {
        // Extract the character count from the license plate
        int[] licenseCount = getCharCount(licensePlate.toLowerCase());
        
        String shortest = null;
        
        for (String word : words) {
            if (matches(licenseCount, getCharCount(word.toLowerCase()))) {
                if (shortest == null || word.length() < shortest.length()) {
                    shortest = word;
                }
            }
        }
        
        return shortest;
    }
    
    private int[] getCharCount(String str) {
        int[] count = new int[26];
        for (char c : str.toCharArray()) {
            if (Character.isLetter(c)) {
                count[c - 'a']++;
            }
        }
        return count;
    }
    
    private boolean matches(int[] licenseCount, int[] wordCount) {
        for (int i = 0; i < 26; i++) {
            if (licenseCount[i] > wordCount[i]) {
                return false;
            }
        }
        return true;
    }
}

Explanation

  1. getCharCount Method: This method takes a string, counts the frequency of each letter, and stores it in an integer array where the index represents the letter (‘a’ corresponds to index 0, ‘b’ to index 1, etc.).
  2. matches Method: This method compares the character count arrays of the license plate and the current word to determine if the word contains at least as many of each letter as the license plate.
  3. Main Method: The main method iterates over each word and uses the helper methods to find and return the shortest completing word.

Time Complexity

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