Cheap and Secure Web Hosting Provider : See Now

# Algorithm to efficiently determine whether a magazine contains all the letters in a search string

, ,
Problem Detail:

Title pretty much states the question, I was looking for some assistance with the following:

You are given a search string and a magazine. You seek to generate all the characters in a search string by cutting them out form the magazine. Give an algorithm to efficiently determine whether a magazine contains all the letters in a search string.

I wrote: "Create a count sort which just buckets every occurrence of each specific letter in the magazine down the line. Then use that to compare vs. the search string. If the magazine contains all the letters in the search string, then great you're done; otherwise you need a new magazine."

I feel like that's not enough of an answer for this problem, can someone help? Thanks!

If this was a real life problem, and the search string contained n letters, while the magazine contained m letters, then this would take O (n + m) in time. Typically you would assume that n is very small compared to m, so this solution would take a lot more time than needed.

I'd create a counted set of the letter in the search string. If that counted set is empty (because the search string was empty) I'm done. Then iterate through the letters in the magazine; if a letter is in the counted set then remove it and I'm done if the set became empty. Otherwise, if the iteration finishes then I have a counted set of all letters that cannot be provided by the search string.

This will usually end quite quickly, long before all the letters in the magazine are examined.