1487. Making File Names Unique

MediumArrayHash TableString

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 the collections 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 increment k 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 (using names[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.
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 Evaluator

Example 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 the names 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 an O(n) term, where n is the number of names in the list.
Inside the loop, the code checks if name exists in the dictionary with if name in d, which is an O(1) operation due to hashing.
If there is a conflict for a name, the code enters into a while loop to find the correct suffix k. In the worst case, it may run as many times as there are names with the same base, let's call this number m.
Each iteration of the while loop involves a string concatenation and a dictionary lookup, both of which are O(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 to 2n entries, contributing O(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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

How does quick sort divide the problem into subproblems?

Divide the array into two equal halves by index

Divide the array into two based on whether an element is smaller than an arbitrary value

Divide the array into a stray element and the rest of the array

Quick sort does not use divide and conquer

I don’t know