Find Words That Can Be Formed by Characters

Problem Description

So, you think you can just throw a bunch of words at a wall and see which ones stick? Well, in the world of programming, that’s not how it works! The problem at hand is to find out how many words from a given list can be formed using a set of characters. Imagine you’re at a party, and you have a limited number of letters to create the perfect party invitation. You can’t just use any letter you find lying around; you have to make do with what you have!

In this LeetCode problem, you’re given a list of words and a string of characters. Your task is to count how many of those words can be formed using the characters in the string. If you think this is easy, just wait until you try to spell “supercalifragilisticexpialidocious” with only a few letters!

Code Solution


class Solution:
    def countCharacters(self, words: list[str], chars: str) -> int:
        ans = 0
        count = collections.Counter(chars)

        for word in words:
            tempCount = count.copy()
            for c in word:
                tempCount[c] -= 1
                if tempCount[c] < 0:
                    ans -= len(word)
                    break
            ans += len(word)

        return ans

Approach

The approach taken in the code is quite straightforward. It uses a Counter from the collections module to count the occurrences of each character in the chars string. For each word in the words list, it checks if the word can be formed by decrementing the count of each character in the temporary count. If any character count goes below zero, it means that the word cannot be formed, and the length of that word is subtracted from the total count. Otherwise, the length of the word is added to the total count.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(N * M), where N is the number of words and M is the average length of the words.
Space Complexity	O(K), where K is the number of unique characters in the `chars` string.

Real-World Example

Imagine you’re trying to create a unique password for your online accounts, but you can only use the letters from your favorite phrase, “Stay Safe!” You have a list of potential passwords, and you want to know how many of them can be created using the letters from your phrase. This problem is just like that! You’re checking if the letters you have can form the words you want, and if not, well, it’s back to the drawing board!