#1487

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Making File Names Unique

This problem requires creating unique folder names by appending suffixes to duplicate names using an array scanning and hash lookup approach.

array hash table string

Problem Statement

Given an array of strings names where each string represents a folder name to be created in sequence, your task is to assign unique names to each folder. If a name has already been assigned, append a suffix of the form (k) to it, where k is the smallest positive integer such that the resulting name is unique.

Return the array of strings where each element represents the actual name assigned to the corresponding folder. For example, if a folder named 'abc' already exists, the next folder named 'abc' will be renamed to 'abc(1)' and so on, with the smallest integer that makes the name unique.

Examples

Example 1

Input: names = ["pes","fifa","gta","pes(2019)"]

Output: ["pes","fifa","gta","pes(2019)"]

Let's see how the file system creates folder names: "pes" --> not assigned before, remains "pes" "fifa" --> not assigned before, remains "fifa" "gta" --> not assigned before, remains "gta" "pes(2019)" --> not assigned before, remains "pes(2019)"

Example 2

Input: names = ["gta","gta(1)","gta","avalon"]

Output: ["gta","gta(1)","gta(2)","avalon"]

Let's see how the file system creates folder names: "gta" --> not assigned before, remains "gta" "gta(1)" --> not assigned before, remains "gta(1)" "gta" --> the name is reserved, system adds (k), since "gta(1)" is also reserved, systems put k = 2. it becomes "gta(2)" "avalon" --> not assigned before, remains "avalon"

Example 3

Input: names = ["onepiece","onepiece(1)","onepiece(2)","onepiece(3)","onepiece"]

Output: ["onepiece","onepiece(1)","onepiece(2)","onepiece(3)","onepiece(4)"]

When the last folder is created, the smallest positive valid k is 4, and it becomes "onepiece(4)".

Constraints

1 <= names.length <= 5 * 104
1 <= names[i].length <= 20
names[i] consists of lowercase English letters, digits, and/or round brackets.

Solution Approach

Use Hash Table for Tracking Names

We maintain a hash table to store the names that have been assigned so far. When a new name is encountered, we check if it's already in the table. If it is, we increment a counter to find the smallest integer k such that the name with the suffix (k) is unique. This approach ensures constant time lookup and insertion.

Array Scanning with Hash Lookup

The problem relies on scanning through the array of names. Each time we encounter a name that already exists, we append the suffix (k) where k is the smallest integer making the name unique. This method combines array scanning and efficient hash table lookups to solve the problem in linear time.

Efficiently Handling Suffix Creation

For each repeated name, we append the suffix (k) by checking the current count of how many times the name has been seen in the hash table. This ensures that the suffix is the smallest possible integer, and the solution is optimized by only needing to track the names and their frequencies.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity is O(n) where n is the length of the names array, as we perform a constant time operation (hash lookup and insertion) for each element in the array. The space complexity is O(n) due to the storage required for the hash table to keep track of the names and their counts.

What Interviewers Usually Probe

Can the candidate explain the trade-off between using a hash table and simpler data structures like arrays?
Does the candidate understand the need for tracking names and suffixes to handle duplicates efficiently?
Can the candidate clearly articulate why the problem requires constant time lookups for scalability?

Common Pitfalls or Variants

Common pitfalls

Not updating the counter for suffix generation correctly, leading to collisions in names.
Using a more complex data structure than necessary (like a list instead of a hash table) that would increase time complexity.
Failing to handle the case where the same name is used multiple times with multiple suffixes, and not properly appending the smallest integer.

Follow-up variants

Instead of appending a number as a suffix, the problem could involve appending letters or symbols to ensure uniqueness.
The input could contain a mixture of already unique names and duplicates, testing the ability to efficiently manage both cases.
The problem could be extended to handle additional constraints, such as large file systems where names need to be stored and updated in real time.

FAQ

How do I handle duplicate names when creating folders?

The solution involves checking each folder name against a hash table to see if it already exists. If it does, append the smallest integer to make it unique.

What is the time complexity of the solution?

The time complexity is O(n), where n is the number of names, as each name is processed in constant time due to hash table lookups.

How do hash tables help solve this problem efficiently?

Hash tables allow for constant time lookup and insertion, making it easy to check for duplicates and generate the correct suffix when needed.

What happens if the same name appears multiple times?

Each time the same name appears, a suffix is added with the smallest integer that ensures the name remains unique. For example, 'name(1)', 'name(2)', etc.

Can this problem be solved using only an array?

While it is possible to use an array, a hash table is much more efficient for this problem, providing faster lookups and inserts.

terminal

Solution

Solution 1: Hash Table

We can use a hash table $d$ to record the minimum available index for each folder name, where $d[name] = k$ means the minimum available index for the folder $name$ is $k$. Initially, $d$ is empty since there are no folders.

class Solution:
    def getFolderNames(self, names: List[str]) -> List[str]:
        d = defaultdict(int)
        for i, name in enumerate(names):
            if name in d:
                k = d[name]
                while f'{name}({k})' in d:
                    k += 1
                d[name] = k + 1
                names[i] = f'{name}({k})'
            d[names[i]] = 1
        return names

Continue Practicing

#1452 people whose list of favorite companies is not a subset of another list #1436 destination city #1418 display table of food orders in a restaurant