Shortest Completing Word

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.

LeetCode Problem - 735

class Solution {

    // Method to find the shortest completing word from the list of words that contains all the letters from the license plate
    public String shortestCompletingWord(String licensePlate, String[] words) {
        Map<Character, Integer> licMap = new HashMap<>();  // Map to store the frequency of characters from the license plate
        String answer = "";  // Variable to store the final answer
        int lengthCheck = Integer.MAX_VALUE;  // Variable to store the minimum length of the completing word

        // Populate the licMap with the character frequencies from the license plate
        for (char ch : licensePlate.toCharArray()) {
            char licLowerCase = Character.toLowerCase(ch);  // Convert character to lowercase
            if (isChar(licLowerCase)) {  // Check if it's a letter
                licMap.put(licLowerCase, licMap.getOrDefault(licLowerCase, 0) + 1);  // Update frequency in the map
            }
        }

        // Loop through each word in the words array
        for (int i = 0; i < words.length; i++) {
            String word = words[i];

            // Create a frequency map for the current word
            Map<Character, Integer> wordMap = new HashMap<>();
            for (int j = 0; j < word.length(); j++) {
                char wordCase = Character.toLowerCase(word.charAt(j));  // Convert character to lowercase
                if (isChar(wordCase)) {  // Check if it's a letter
                    wordMap.put(wordCase, wordMap.getOrDefault(wordCase, 0) + 1);  // Update frequency in the map
                }
            }

            // Check if the word satisfies the conditions of being a "completing word"
            boolean flag = true;
            for (char licKey : licMap.keySet()) {
                int val1 = licMap.get(licKey);  // Frequency of character in license plate
                int val2 = -1;

                // Check if the word contains the required character with the correct frequency
                if (wordMap.get(licKey) != null) {
                    val2 = wordMap.get(licKey);  // Frequency of character in the word
                    if (!(val1 <= val2)) {  // If the word doesn't have enough occurrences of the character
                        flag = false;
                        break;  // Exit the loop as this word is not valid
                    }
                } else {
                    flag = false;  // If the word doesn't contain the required character
                    break;
                }
            }

            // Update the answer if this word is a valid completing word and is shorter than the previous found words
            if (flag && (word.length() < lengthCheck)) {
                answer = word;
                lengthCheck = word.length();
            }
        }

        return answer;  // Return the shortest completing word
    }

    // Helper method to check if a character is a letter
    public boolean isChar(char ch) {
        return Character.isLetter(ch);  // Return true if the character is a letter, false otherwise
    }
}