1487. Making File Names Unique
Problem Description
The problem requires creating a file system with folders named according to the input array names
. Whenever a folder is created, it should have a unique name. If a name has been used before, a suffix in the format of (k)
must be appended, where k
is the smallest positive integer that makes the name unique again. The task is to simulate this process and return the final list of names used for the folders.
For instance, if names
is ["doc", "doc", "image", "doc(1)", "doc"], the output should be ["doc", "doc(1)", "image", "doc(1)(1)", "doc(2)"]. This array represents the names of the folders after every minute following the naming rules defined by the problem.
Intuition
The intuition behind the solution involves tracking each folder name and the suffixes applied to resolve the name conflicts. We use a dictionary (hashmap) to keep track of the names and their corresponding suffixes to achieve this efficiently.
We iterate over the input list of names. For each name, we perform the following steps:
-
Check if the name already exists: If the name exists in the dictionary, it means we've encountered a conflict and we need to find the next suitable suffix to make the name unique.
-
Resolve the conflict: Increase the numeral suffix starting from the one recorded in the dictionary until we find a name that is not already used.
-
Update the name with the suffix: Once a unique name is constructed, we update the current name in the list of names with the newly formed unique name.
-
Update the dictionary: Store the changed name with a suffix of 1 if it's a new name. If the name was altered and had a suffix added, update the original conflicting name's suffix for future conflict resolution.
The logic behind incrementing the suffix numeral ensures that we will always find the smallest possible integer k
to append while maintaining uniqueness. The defaultdict from the collections module provides convenience for this process since it will automatically assume the default integer value of 0 when accessing a new name not yet in the dictionary.
By the end of the input list iteration, we have a list representing the actual names the system has assigned to each folder.
Solution Approach
The implementation of the provided solution uses a combination of a loop and a dictionary (hashmap) to achieve its objectives. Here's a step-by-step explanation of how the code works:
-
Data Structure: We use a
defaultdict
from thecollections
module with integer values that defaults to 0. This helps in easily tracking the next available integer suffix that should be used for each unique base name. -
Iterate Through Names: We iterate over the input list of names with the help of a
for
loop. Each name encountered is evaluated to determine if it's unique or if a suffix is needed. -
Check and Resolve Name Conflicts:
- If the current name is present in the dictionary, it indicates a conflict. We then initiate a while loop to find a unique name by incrementing the integer suffix.
- Inside the loop
(while f'{name}({k})' in d)
, we keep appending a suffix(k)
to the original name and incrementk
to find a non-conflicting name. - Once a unique name is found, we assign this new name to the correct position in the
names
list (usingnames[i] = f'{name}({k})'
) and update the dictionary with the new suffix(d[name] = k + 1)
to indicate the next available suffix for this base name.
-
Final Names Update and Dictionary Maintenance:
- If the current name isn't in the dictionary, it's already unique, and we simply store it with a suffix of 1 (which means
d[names[i]] = 1
) in the dictionary for potential future conflicts. - If the name was modified by adding a suffix, we've already updated the entry in the dictionary with the next suffix to be used.
- If the current name isn't in the dictionary, it's already unique, and we simply store it with a suffix of 1 (which means
-
End of Loop: Each iteration of the loop either adds a unique name directly to the dictionary or resolves a conflict by appending the appropriate suffix. By the end of the loop, all conflicts are resolved.
-
Return the Modified List: The
names
list, which now contains all the unique names assigned by the system, is returned at the end of the function.
This solution's complexity lies in the loop and the operations within it. The average case time complexity is O(n*k), where n
is the length of the names
list and k
represents the time taken to find a unique name through the incremental suffix process. However, the worst-case time complexity can increase if there is a large number of conflicts that result in longer searches for a unique name.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's use a small example to illustrate the solution approach. Consider the input array names
as ["file", "file", "file", "file"]
. The aim is to create a list where all folder names are unique following the rules described in the problem statement.
-
Start with an empty
defaultdict
and iterate through thenames
list. -
First, encounter "file". "file" is not in the dictionary, so we add "file" to the dictionary with a value of 1 (meanwhile it's also added to our final names list).
Updated names list:
["file"]
Dictionary:{"file": 1}
-
Next, see another "file". Since "file" is in the dictionary (with a value
1
), there's a conflict. We append(1)
to "file" to resolve this, resulting in "file(1)".Updated names list:
["file", "file(1)"]
Dictionary before incrementing:{"file": 1}
Increment the suffix in the dictionary:{"file": 2}
(for potential future conflicts) -
Encounter another "file". Check the dictionary. Since "file" is there with the value
2
, append(2)
and increment the suffix.Updated names list:
["file", "file(1)", "file(2)"]
Dictionary:{"file": 3}
-
We see "file" again. Repeat the check and update steps, the suffix this time is
(3)
.Final names list:
["file", "file(1)", "file(2)", "file(3)"]
Final dictionary:{"file": 4}
-
The iteration ends as there are no more names in the
names
array.
Our final list is ["file", "file(1)", "file(2)", "file(3)"]
, where each "file" is unique. This shows how the aforementioned algorithm successfully solves the file naming problem by systematically ensuring each new folder name has not been used before, appending the smallest possible unique suffix when necessary.
Solution Implementation
1from collections import defaultdict
2
3class Solution:
4 def getFolderNames(self, names: List[str]) -> List[str]:
5 # Create a dictionary to store the counts of each folder name.
6 name_counts = defaultdict(int)
7
8 # Iterate over all the names in the input list.
9 for index, name in enumerate(names):
10 # Check if the name already exists in the dictionary.
11 if name in name_counts:
12 # Start with the current count for this name.
13 count = name_counts[name]
14 # Check if the name with the appended count exists.
15 # If it does, increment the count and check again.
16 while f'{name}({count})' in name_counts:
17 count += 1
18 # Update the count for this name in the dictionary.
19 name_counts[name] = count + 1
20 # Modify the current name to include the count in the format "name(count)".
21 names[index] = f'{name}({count})'
22 # Add or update the name in the dictionary with a count of 1,
23 # indicating this modified name is now used once.
24 name_counts[names[index]] = 1
25
26 # Return the list with unique folder names.
27 return names
28
1class Solution {
2 public String[] getFolderNames(String[] names) {
3 // Create a map to store the highest integer k used for each original name.
4 Map<String, Integer> nameMap = new HashMap<>();
5
6 // Iterate through each name in the input array.
7 for (int i = 0; i < names.length; ++i) {
8 // If the current name has already been encountered,
9 // append a unique identifier to make it distinct.
10 if (nameMap.containsKey(names[i])) {
11 // Get the current highest value of k used for this name.
12 int k = nameMap.get(names[i]);
13 // Check if the name with the appended "(k)" already exists.
14 // If it does, increment k until a unique name is found.
15 while (nameMap.containsKey(names[i] + "(" + k + ")")) {
16 ++k;
17 }
18
19 // Update the map with the new highest value of k for this name.
20 nameMap.put(names[i], k);
21 // Modify the current name by appending "(k)" to make it unique.
22 names[i] += "(" + k + ")";
23 }
24
25 // Insert or update the current name in the map, setting its value to 1.
26 // If the name is new, this records it as seen for the first time.
27 // If the name has been modified, this ensures it's treated as new.
28 nameMap.put(names[i], 1);
29 }
30
31 // Return the modified array of names, with each name now unique.
32 return names;
33 }
34}
35
1#include <vector>
2#include <string>
3#include <unordered_map>
4using namespace std;
5
6class Solution {
7public:
8 vector<string> getFolderNames(vector<string>& names) {
9 unordered_map<string, int> nameCountMap; // Map to keep a count of folder names
10
11 for (auto& name : names) {
12 // Check if 'name' already appeared and get its count
13 int count = nameCountMap[name];
14
15 if (count > 0) {
16 // If name exists, find a unique name by appending the count in parentheses
17 string newName;
18 do {
19 count++; // Increment the count
20 newName = name + "(" + to_string(count) + ")";
21 } while (nameCountMap[newName] > 0); // Check if the newName is also taken, continue if yes
22
23 nameCountMap[name] = count; // Update count for the original name
24 name = newName; // Use the newName for the current iteration
25 }
26
27 // If name is original or new unique name is found, set its count to 1
28 nameCountMap[name] = 1;
29 }
30
31 return names; // Return the vector with unique folder names
32 }
33};
34
1function getFolderNames(names: string[]): string[] {
2 // Initialize a map to keep track of the counts of each folder name
3 const nameCounts: Map<string, number> = new Map();
4
5 // Iterate over the list of names
6 for (let i = 0; i < names.length; ++i) {
7 // Check if the current name already exists in the map
8 if (nameCounts.has(names[i])) {
9 // Retrieve the count for the current name, defaulting to 0 if it's not found
10 let count: number = nameCounts.get(names[i]) || 0;
11
12 // Create a unique folder name by appending count in parentheses
13 // Keep incrementing count until a unique name is found
14 while (nameCounts.has(`${names[i]}(${count})`)) {
15 ++count;
16 }
17
18 // Update the count for the current name in the map
19 nameCounts.set(names[i], count);
20
21 // Append the count to the current folder name to make it unique
22 names[i] += `(${count})`;
23 }
24
25 // Set the count for this unique folder name in the map, or update it to 1
26 nameCounts.set(names[i], 1);
27 }
28 // Return the transformed list of names with all unique folders
29 return names;
30}
31
Time and Space Complexity
The provided code snippet maintains a dictionary to keep track of the number of times a particular folder name has appeared. It then generates unique names by appending a number in parentheses if necessary. Let's analyze the time and space complexity:
Time Complexity
- The
for
loop iterates through each name in the input list, so it gives us anO(n)
term, wheren
is the number of names in the list. - Inside the loop, the code checks if
name
exists in the dictionary withif name in d
, which is anO(1)
operation due to hashing. - If there is a conflict for a name, the code enters into a
while
loop to find the correct suffixk
. In the worst case, it may run as many times as there are names with the same base, let's call this numberm
. - Each iteration of the
while
loop involves a string concatenation and a dictionary lookup, both of which areO(1)
operations.
The while
loop could contribute significantly to the time complexity if there are many names with the same base. If m
is the maximum number of duplicates for any name, the worst-case time complexity for while
loop iterations across the entire input is O(m*n)
because each unique name will go through the loop at most m
times.
Therefore, the overall worst-case time complexity is O(n + m*n)
which simplifies to O(m*n)
.
Space Complexity
The space complexity of the algorithm can be broken down as:
- The dictionary
d
, which stores each unique folder name. In the worst case (all folder names are unique, and for each original name, there’s a different number of folders), this dictionary could potentially store 2 entries per name (the original and the latest modified version). So, in the worst case, it could hold up to2n
entries, contributingO(n)
to the space complexity. - Temporary storage for constructing new folder names during the
while
loop does not significantly add to the space complexity because it only holds a single name at a time.
Therefore, the overall space complexity is O(n)
.
To summarize:
- Time Complexity:
O(m*n)
- Space Complexity:
O(n)
Learn more about how to find time and space complexity quickly using problem constraints.
How many times is a tree node visited in a depth first search?
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.