Allocate Unique File Names in an In-Memory Vault

An in-memory file vault must assign a unique name whenever a file is created. If the requested name already exists, append a parenthesized positive integer to obtain an unused name.

Implement allocate_names(requests: string[]) -> string[] and return the assigned name for each request in order.

Constraints & Assumptions

• All requests target the same namespace, which starts empty. No file is deleted or renamed during the sequence.
• If requested name s is unused, assign s unchanged.
• Otherwise choose the smallest positive integer x for which s + "(" + decimal(x) + ")" is unused, then reserve and return that name.
• Names are case-sensitive, nonempty ASCII strings of at most 100 characters. There are at most 10,000 requests.
• Parentheses already present in a requested name are literal text. For example, a collision on a(1) tries a(1)(1); do not reinterpret it as a collision on a.
• The smallest available positive suffix and flat namespace are explicit practice choices for the reported duplicate-name behavior.

Examples

requests = ["report", "report", "report", "report(1)"]
result = ["report", "report(1)", "report(2)", "report(1)(1)"]

requests = ["a(1)", "a", "a", "A"]
result = ["a(1)", "a", "a(2)", "A"]

Hint: Remember where each repeated base can resume

Once a suffix candidate is known to be occupied and names are never removed, trying the same candidate again for that base cannot succeed.

Allocate Unique File Names with the Smallest Positive Suffix

Approach

Use a hash map whose keys are reserved names and whose value is the next suffix to try when that exact name is requested again. An unused request is reserved unchanged with cursor one. On a collision, test candidates formed by appending a canonical positive decimal suffix to the entire requested text. Advance past occupied names, reserve the first unused candidate, and save the next suffix for the original base. Every suffix below a saved cursor has already been found occupied or allocated; because there is no deletion, those suffixes can never become available. Starting at that cursor therefore still yields the smallest valid positive suffix. Initializing every newly reserved name with its own cursor handles later direct requests for generated names and nested parentheses. A given base never retries a suffix. Across bases, a canonical final parenthesized integer uniquely identifies the base obtained by removing that final component, so an already-reserved spelling can cause at most one failed suffix probe in the entire run. Thus there are O(N) expected hash-table probes over N requests. If L bounds candidate spelling length, construction and hashing give O(NL) expected time and O(NL) stored characters, including output. L is at most the maximum request length plus O(log(N+1)) suffix characters; generated names are not truncated.

• Time complexity: O(NL) expected time, where L bounds constructed name length; O(N) expected hash-table probes.
• Space complexity: O(NL) characters for reserved names and returned output.