Skip to main content
Talentd

Making File Names Unique - Solution & Explanation

MediumArrayHash TableString14 min readAsked at: Okta
Practice this problem

Problem Statement

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 * 104
  • 1 <= names[i].length <= 20
  • names[i] consists of lowercase English letters, digits, and/or round brackets.

Approach Overview

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.

Approach 1: HashMap to Track Folder Names

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.

Code

PythonJava

Python

Java

Complexity

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.

Try this approach in the editor →

Approach 2: Two-pass Approach with Back-Checking

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.

Code

C++JavaScript

C++

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 3: 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.

Next, we iterate through the folder names array. For each file name name:

  • If 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).
  • If name is not in d, we can directly add name to d and set d[name] to 1.
  • Then, we add 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 names array 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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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.
Space Complexity: O(n) due to the storage of names in the hashmap.

Two-pass Approach with Back-Checking

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.

Hash Table—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
HashMap to Track Folder NamesO(n) averageO(n)Best general solution. Efficient when many duplicates appear.
Two-pass Approach with Back-CheckingO(n * k) worst caseO(n)Simple implementation when duplicate frequency is small.

Video Solution

1487. Making File Names Unique (python) (Leetcode Medium) • Programming Live with Larry • 991 views views

Watch 5 more video solutions →

Frequently Asked Questions

Is Making File Names Unique easy or hard?
The problem is considered Medium difficulty on LeetCode. The main challenge is handling repeated duplicates efficiently and avoiding repeated suffix checks. Once you recognize the need to track the next suffix index with a hash map, the implementation becomes straightforward.
Making File Names Unique Python/Java solution
Both Python and Java implementations typically use a dictionary or HashMap to store name counts and generated names. Each iteration checks if the current name exists, generates suffix variants if needed, and updates the map with the final unique name.
How to solve Making File Names Unique in O(n)?
Maintain a hash map where the key is a file name and the value is the next suffix index to try. When a duplicate appears, generate names like name(k) using the stored index and update the map once a free name is found. This avoids repeatedly testing already used suffixes and keeps operations near constant time.
What is the best approach for Making File Names Unique?
The most efficient solution uses a hash map that stores each used file name and the next available suffix index. When a duplicate appears, the algorithm jumps directly to the next unused suffix instead of checking from (1) every time. This reduces redundant checks and keeps the overall complexity close to O(n).
Is Making File Names Unique asked at Google/Amazon/Meta?
Problems involving hash maps, collision handling, and string manipulation frequently appear in interviews at companies like Google, Amazon, and Meta. Variants of this question test how well candidates manage duplicates and optimize lookups using hash-based data structures.
What data structure is used in Making File Names Unique?
A hash map (or dictionary) is the core data structure. It stores previously used file names and tracks the next available suffix for each base name. Hash tables provide O(1) average lookup and insertion, which makes the algorithm efficient.
What is the time complexity of Making File Names Unique?
Using the optimized hash map suffix-tracking method, the time complexity is O(n) on average because each name is processed once with constant-time hash lookups. The space complexity is also O(n) since every generated name must be stored in the map.

Ready to solve this problem?

Practice Making File Names Unique with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays