ūüĎč
Welcome to my blog!

Generate Document

Learn how to verify if a given document can be generated from a set of characters with practical algorithmic approach.

Generate Document
Strings
easy

Published At

6/4/2021

Reading Time

~ 3 min read

You're given a string of available characters and a string representing a document that you need to generate. Write a function that determines if you can generate the document using the available characters. If you can generate the document, your function should return true; otherwise, it should return false.

You're only able to generate the document if the frequency of unique characters in the characters string is greater than or equal to the frequency of unique characters in the document string. For example, if you're given characters = "abcabc" and document = "aabbccc" you cannot generate the document because you're missing one c.

The document that you need to create may contain any characters, including special characters, capital letters, numbers, and spaces.

Note: you can always generate the empty string ("").

Sample Input

jscharacters = "Bste!hetsi ogEAxpelrt x "
document = "AlgoExpert is the Best!"
jscharacters = "Bste!hetsi ogEAxpelrt x "
document = "AlgoExpert is the Best!"

Sample Output

jstrue
jstrue

Hints

Hint 1

There are multiple ways to the solve this problem, but not all approaches have an optimal time complexity. Is there any way to solve this problem in better than O(m * (n + m)) or O(n * (n + m)) time, where n is the length of the characters string and m is the length of the document string?

Hint 2

One of the simplest ways to solve this problem is to loop through the document string, one character at a time. At every character, you can count how many times it occurs in the document string and in the characters string. If it occurs more times in the document string than in the characters string, then you cannot generate the document. What is the time complexity of this approach?

Hint 3

The approach discussed in Hint #2 runs in O(m * (n + m)) time. Can you use some external space to optimize this time complexity?

Hint 4

You can solve this problem in O(n + m) time. To do so, you need to use a hash table. Start by counting all of the characters in the characters string and storing these counts in a hash table. Then, loop through the document string, and check if each character is in the hash table and has a value greater than zero. If a character isn't in the hash table or doesn't have a value greater than zero, then you cannot generate the document. If a character is in the hash table and has a value greater than zero, then decrement its value in the hash table to indicate that you've "used" one of these available characters. If you make it through the entire document string without returning false, then you can generate the document.

Optimal Space & Time Complexity

O(n + m) time | O(c) space - where n is the number of characters, m is the length of the document, and c is the number of unique characters in the characters string

Solution-1
jsfunction generateDocument(characters, document) {
	if (document === "") return true;
	
	for (let character of document) {
		if (characters.indexOf(character) !== -1) {
			characters = characters.replace(character, '');
		} else {
			return false;
		}
	}
	
  return true;
}
Solution-1
jsfunction generateDocument(characters, document) {
	if (document === "") return true;
	
	for (let character of document) {
		if (characters.indexOf(character) !== -1) {
			characters = characters.replace(character, '');
		} else {
			return false;
		}
	}
	
  return true;
}

ūüź≤

Do you have any questions, or simply wish to contact me privately? Don't hesitate to shoot me a DM on Twitter.

Have a wonderful day.
Abhishek ūüôŹ

Join My Exclusive Newsletter Community

Step into a world where creativity intersects with technology. By subscribing, you'll get a front-row seat to my latest musings, full-stack development resources, and exclusive previews of future posts. Each email is a crafted experience that includes:

  • In-depth looks at my covert projects and musings to ignite your imagination.
  • Handpicked frontend development resources and current explorations, aimed at expanding your developer toolkit.
  • A monthly infusion of inspiration with my personal selection of quotes, books, and music.

Embrace the confluence of words and wonder, curated thoughtfully and sent straight to your inbox.

No fluff. Just the highest caliber of ideas.