Generate Document

Category

Strings

Difficulty

Easy

Problem Statement

Given a string of available characters and a document string, determine whether the characters in the available string are sufficient to generate the document. Each character in the available string can only be used once. The function should return true if the document can be generated and false otherwise.

Intuition

Generating the document is possible if and only if every character required by the document appears at least as many times in the available characters. This is a straightforward frequency comparison: count how often each character appears in both strings and verify that the supply meets or exceeds the demand for every character.

Approach

1. Build a frequency map for the characters string (the available supply).
2. Build a frequency map for the document string (the required demand).
3. For each character in the document frequency map:
   • If its count exceeds the corresponding count in the characters frequency map (defaulting to 0 if absent), return false.
4. If all checks pass, return true.

Pseudocode

function generateDocument(characters, document):
    charFreq = frequencyMap(characters)

    for char in document:
        if charFreq.getOrDefault(char, 0) <= 0:
            return false
        charFreq[char] = charFreq[char] - 1

    return true

Time & Space Complexity

• Time: O(n + m) where n is the length of the characters string and m is the length of the document. Building the frequency map is O(n) and iterating through the document is O(m).
• Space: O(c) where c is the number of unique characters in the characters string. For a fixed alphabet this is O(1).

Key Insights

• The problem is equivalent to checking if the character frequency multiset of the document is a subset of the character frequency multiset of the available characters.
• Spaces and special characters count as characters and must also be available in sufficient quantity.
• An alternative approach decrements counts while iterating through the document, returning false immediately if a count drops below zero.

Edge Cases

• Empty document: always return true regardless of available characters (no characters needed).
• Empty characters string with non-empty document: return false.
• Both strings empty: return true.
• Document contains characters not present in the characters string at all: return false.
• Document requires more of a character than available: return false.