Given an array of strings names of size n. You will create n folders in your file system such that, at the ith minute, you will create a folder with the name names[i].
Since two files cannot have the same name, if you enter a folder name that was previously used, the system will have a suffix addition to its name in the form of (k), where, k is the smallest positive integer such that the obtained name remains unique.
Return an array of strings of length n where ans[i] is the actual name the system will assign to the ith folder when you create it.
Example 1:
Input: names = ["pes","fifa","gta","pes(2019)"] Output: ["pes","fifa","gta","pes(2019)"] Explanation: 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"] Explanation: 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)"] Explanation: When the last folder is created, the smallest positive valid k is 4, and it becomes "onepiece(4)".
Constraints:
1 <= names.length <= 5 * 1041 <= names[i].length <= 20names[i] consists of lowercase English letters, digits, and/or round brackets.Problem Overview: You receive a list of folder or file names. When a name already exists, the system must create a new unique name by appending a suffix like (k) where k is the smallest positive integer that keeps the name unique. The goal is to process the list and return the final unique names while preserving order.
Approach 1: HashMap to Track Folder Names (O(n) average time, O(n) space)
This approach uses a hash map to track previously used names and the next available suffix for each base name. Iterate through the input array once. If the current name has not been seen, store it in the map with suffix index 1. If it already exists, repeatedly generate names like name(k) and check the map until a free one appears. Store both the generated name and the updated suffix index in the map so future collisions skip directly to the next candidate. Hash lookups make each check O(1) on average, giving near O(n) total time.
The key insight is remembering the next suffix for each base name. Without this optimization, you'd repeatedly test (1), (2), (3) even if those suffixes were already used. Tracking the next candidate prevents unnecessary retries. This method relies heavily on a hash table for constant-time lookups and works well with sequential iteration of the array.
Approach 2: Two-pass Approach with Back-Checking (O(n * k) worst case, O(n) space)
The two-pass strategy first records all names encountered, then resolves duplicates by checking suffix variations when collisions occur. During iteration, if a name already exists, incrementally test name(1), name(2), and so on until an unused name is found. Each candidate requires a lookup in a hash structure that stores all assigned names.
This approach is simpler conceptually but can degrade in worst-case scenarios when many duplicates appear. For example, if a name repeats hundreds of times, the algorithm may repeatedly check many suffix values. Each lookup is still constant time using a string key in a hash set, but the repeated suffix generation increases total work.
Recommended for interviews: The HashMap suffix-tracking approach is the expected solution. It demonstrates efficient state tracking and avoids redundant work by remembering the next valid suffix for every base name. Interviewers usually accept the simpler back-checking method first, but optimizing it with suffix pointers shows stronger algorithmic thinking and understanding of hash-based indexing.
This approach uses a HashMap to keep track of the folder names that have been created. As you iterate through the input list, check if the name already exists in the map. If it does, find the smallest integer k such that appending (k) to the name results in a name not present in the map. Add this new name to the map. This ensures each folder name is unique.
This Python solution uses a dictionary to keep a count of how many times each base name has been used. If a name is already in the dictionary, it finds the smallest k such that the new name formed by appending (k) is not in the dictionary. The new name is added to the results list and is also added to the dictionary if k is incremented.
Time Complexity: O(n) where n is the number of names. Each operation in the dictionary is O(1) on average.
Space Complexity: O(n) due to the storage of names in the hashmap.
In this approach, we use a set to quickly check the existence of a base name and update the base name to reflect any previous names that were taken. By first checking unique existence and then resolving conflicts, this method attempts to minimize additional searches for a base name suffix.
This C++ implementation uses an unordered map to track the folder names similar to the previous method but addresses the creation of new names dynamically as the checks are performed. This involves finding a new name when a name repeats and ensuring all previously created folder names are kept.
C++
JavaScript
Time Complexity: O(n) where n is the number of names.
Space Complexity: O(n) due to the space needed to store the names and their counts.
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.
Next, we iterate through the folder names array. For each file name name:
name is already in d, it means the folder name already exists, and we need to find a new folder name. We can keep trying name(k), where k starts from d[name], until we find a folder name name(k) that does not exist in d. We add name(k) to d, update d[name] to k + 1, and then update name to name(k).name is not in d, we can directly add name to d and set d[name] to 1.name to the answer array and continue to the next file name.After traversing all file names, we obtain the answer array.
In the code implementation below, we directly modify the
namesarray without using an extra answer array.
The complexity is O(L), and the space complexity is O(L), where L is the sum of the lengths of all file names in the names array.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| HashMap to Track Folder Names | Time Complexity: O(n) where n is the number of names. Each operation in the dictionary is O(1) on average. |
| Two-pass Approach with Back-Checking | Time Complexity: O(n) where n is the number of names. |
| Hash Table | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| HashMap to Track Folder Names | O(n) average | O(n) | Best general solution. Efficient when many duplicates appear. |
| Two-pass Approach with Back-Checking | O(n * k) worst case | O(n) | Simple implementation when duplicate frequency is small. |
1487. Making File Names Unique (python) (Leetcode Medium) • Programming Live with Larry • 973 views views
Watch 5 more video solutions →Practice Making File Names Unique with our built-in code editor and test cases.
Practice on FleetCode