Is Find Words That Can Be Formed by Characters easy or hard?

Find Words That Can Be Formed by Characters is classified as an Easy problem on LeetCode with a high acceptance rate around 70%. The challenge mainly tests understanding of character counting, arrays, and hash maps rather than complex algorithms.

Find Words That Can Be Formed by Characters Python/Java solution

Python and Java implementations typically create an array or dictionary to store character frequencies of the given string. For each word, compute its frequency and verify it does not exceed the base counts. If valid, add the word length to the result. The algorithm remains O(W * K) in both languages.

How to solve Find Words That Can Be Formed by Characters in O(n)?

Build a frequency counter for the characters string, then iterate through each word and count its characters. For every character in the word, check if its frequency exceeds the available count. If all checks pass, add the word length to the answer. Since counting and comparisons are linear in word length, the overall complexity stays O(W * K).

What is the best approach for Find Words That Can Be Formed by Characters?

The most efficient approach uses character frequency counting with a fixed array of size 26. Count the frequency of characters in the input string and compare it with the frequency of each word. If every character in the word appears within the available count, add its length to the total. This approach runs in O(W * K) time and O(1) space.

Is Find Words That Can Be Formed by Characters asked at Google/Amazon/Meta?

Problems involving character frequency counting and hash maps frequently appear in interviews at companies like Amazon, Google, and Meta. While this exact problem may vary, the underlying pattern—verifying resource availability using frequency arrays—is a common interview concept.

What data structure is used in Find Words That Can Be Formed by Characters?

The typical solution uses a frequency array of size 26 to store counts of lowercase letters. Some implementations use a hash map instead, especially when the character set is not restricted. Both approaches rely on counting and quick lookup of character frequencies.

What is the time complexity of Find Words That Can Be Formed by Characters?

The time complexity is O(W * K), where W is the number of words and K is the average length of each word. Each word is scanned once to compute its character counts and compared against the base frequency array built from the characters string.

Description Hints 4 Solution Video 7:23

1160. Find Words That Can Be Formed by Characters

Easy71.5% acceptance7 companies

You are given an array of strings words and a string chars.

A string is good if it can be formed by characters from chars (each character can only be used once).

Return the sum of lengths of all good strings in words.

Example 1:

Input: words = ["cat","bt","hat","tree"], chars = "atach"
Output: 6
Explanation: The strings that can be formed are "cat" and "hat" so the answer is 3 + 3 = 6.

Example 2:

Input: words = ["hello","world","leetcode"], chars = "welldonehoneyr"
Output: 10
Explanation: The strings that can be formed are "hello" and "world" so the answer is 5 + 5 = 10.

Constraints:

1 <= words.length <= 1000
1 <= words[i].length, chars.length <= 100
words[i] and chars consist of lowercase English letters.

Asked at 7 companies

PayPal Karat

Google Amazon Microsoft Meta Bloomberg

Topics

Hints open one at a time

Hint 1

Solve the problem for each string in words independently.

Hint 2

Now try to think in frequency of letters.

Hint 3

Count how many times each character occurs in string chars.

Hint 4

To form a string using characters from chars, the frequency of each character in chars must be greater than or equal the frequency of that character in the string to be formed.

7:23

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution