Shortest Completing Word

The idea to solve this problem is to first create a histogram of characters for the license plate. Then, for each word, and for each character of the word, check if it exists in our histogram and if it is, then reduce the count. If the total sum of the histogram is zero then that means the word completes our license plate and is a candidate for the answer. We have to go through all the words and keep track of the shortest one which will be our final answer.

class Solution {
    fun shortestCompletingWord(licensePlate: String, words: Array<String>): String {
        var licenseChars = IntArray(26)
        var smallest = ""
        licensePlate.toLowerCase().forEach {
            if(Character.isLetter(it)) licenseChars[it - 'a']++
        }

        words.forEach { word ->
            val x = licenseChars.clone()
            
            word.forEach {
                if(x[it - 'a'] > 0) x[it - 'a']--
                
            }
            
            if(x.sum() == 0) {
                smallest = if(smallest.isNotEmpty() && smallest.length <= word.length) smallest else word
            }
        }
        
        return smallest
    }
}
Runtime: 212 ms, faster than 83.33% of Kotlin online submissions for Shortest Completing Word.
Memory Usage: 36.7 MB, less than 100.00% of Kotlin online submissions for Shortest Completing Word.
comments powered by Disqus