Position: SDE1

Given a list of words and list of letters. Words can be formed by using letters given and each letter can only be used once. Find maximum number of letters that can be used from the given list to form the words from the word list.

Example 1:

Input: words = ["dog", "og", "cat"], letters = ['o', 'g', 'd']
Output: ["dog"]
Explanation: Using the given letters we can form ["dog"] and ["og"] but output the longer word

Example 2:

Input: words =[ "dog", "do", "go"], letters = ["d", "o", "g", "o"]
Output: ["do", "go"]
Explanation: Here we can either form ["dog"] or ["do", "go"] but pick the one which requires more letters.

Was asked to solve in O(n). But could not come up with the required solution. Any leads on how to solve this?