Leetcode 1487. Making File Names Unique

Problem Explanation

In this problem, we are given an array of initial folder names. We are required to create folders with these names in a filesystem. However, the filesystem does not allow two folders to have the same name. If we try to create a folder with a name that already exists, the system will append a suffix in the form (k), where k is the smallest positive integer such that this modified name hasn't been used before.

We are required to return an array of the actual names assigned by the system to the folders.

For example, if the initial folder names are ["one", "one", "two", "two", "two", "three"], the system will name the folders as ["one", "one(1)", "two", "two(1)", "two(2)", "three"].

Solution Approach

The problem can be solved using the concept of hashing. The general idea is to keep a hashmap, nameToSuffix, where for a given name, we store the current maximum suffix that was used.

For each name in the provided list, we check if it is already used by looking up in our nameToSuffix map. If it is not present, we add this name to the map and initialize its suffix value as 0.

If the name is already used, we increment its suffix value and append the incremented suffix to the name. If this new name is also already used, we keep on incrementing the suffix until we obtain a unique name.

This new name is stored as a folder name and is also added to the nameToSuffix map with a suffix of 0.

Example Walkthrough

Let's walkthrough this approach using names = ["gta","gta(1)","gta","avalon"]:

1. We initialize nameToSuffix as empty and start with the first name, "gta". Since it's not used before, we add it to the nameToSuffix and set its corresponding suffix value to 0.

2. Move on to "gta(1)". Again, it is a new name, so add to nameToSuffix with a suffix value of 0.

3. Then, we move to the third "gta". This name is seen before, so we increment the corresponding suffix value in nameToSuffix, which gives us 1. But "gta(1)" is also used before, hence we increment the suffix value again to get 2. "gta(2)" is a new name. So, append this to our answer and add to nameToSuffix.

4. Finally, we have "avalon". As it is a new name, add to nameToSuffix and append to our answer.

5. Thus, our final answer is ["gta","gta(1)","gta(2)","avalon"].

C++ Solution

1
2cpp
3class Solution {
4public:
5  vector<string> getFolderNames(vector<string>& names) {
6    vector<string> ans;
7    unordered_map<string, int> nameToSuffix;
8
9    for (const string& name : names)
10      if (const auto it = nameToSuffix.find(name); it != cend(nameToSuffix)) {
11        int suffix = it->second;
12        string newName = getName(name, ++suffix);
13        while (nameToSuffix.count(newName))
14          newName = getName(name, ++suffix);
15        nameToSuffix[name] = suffix;
16        nameToSuffix[newName] = 0;
17        ans.push_back(newName);
18      } else {
19        nameToSuffix[name] = 0;
20        ans.push_back(name);
21      }
22
23    return ans;
24  }
25
26private:
27  string getName(const string& name, int suffix) {
28    return name + "(" + to_string(suffix) + ")";
29  }
30};

Python Solution

1
2python
3class Solution:
4    def getFolderNames(self, names: List[str]) -> List[str]:
5        d=collections.defaultdict(int)
6        ans = []
7        for name in names:
8            if d[name]==0:
9                ans.append(name)
10                d[name] = 1
11            else:
12                while True:
13                    new_name = name + "("+str(d[name])+")"
14                    d[name] += 1
15                    if d[new_name]==0:
16                        ans.append(new_name)
17                        d[new_name] = 1
18                        break
19        return ans

Java Solution

1
2java
3class Solution {
4    public String[] getFolderNames(String[] names) {
5        String[] result = new String[names.length];
6        HashMap<String, Integer> map = new HashMap<>();
7        for (int i = 0; i < names.length; i++) {
8            String name = names[i];
9            if (!map.containsKey(name)) {
10                map.put(name, 0);
11                result[i] = name;
12            } else {
13                int prev = map.get(name);
14                while (map.containsKey(name + "(" + (prev+1) + ")")) {
15                    prev++;
16                }
17                String newName = name + "(" + (prev+1) + ")";
18                map.put(newName, 0);
19                map.put(name, prev+1);
20                result[i] = newName;
21            }
22        }
23        return result;
24    }
25}

JavaScript Solution

1
2javascript
3var getFolderNames = function(names) {
4  let nameCount = new Map();
5  let res = [];
6  
7  for(let i = 0; i < names.length; i++){
8    let name = names[i];
9    if(!nameCount.has(name)){
10      res.push(name);
11      nameCount.set(name, 1);
12    }
13    else{
14      while(nameCount.has(`${name}(${nameCount.get(name)})`)){
15        nameCount.set(name, nameCount.get(name) + 1);
16      }
17      let newName = `${name}(${nameCount.get(name)})`;
18      res.push(newName);
19      nameCount.set(newName, 1);
20      nameCount.set(name, nameCount.get(name) + 1);
21    }
22  }
23  return res;
24};

Hence, this problem gets solved by using the concept of hashing, implemented using the Map or HashMap data structure, where the map contains each already assigned folder name as a key with its largest used suffix as its value.The algorithm iterates over the list of names and for each name, it checks the map. If the name exists in the map, it means the name was used before, so it increments the suffix, adds the suffix to the name and checks again in the map. If the new modified name was used before, it keeps incrementing the suffix until it finds a name that was not used before. This new name is then added to the result.

If the name was not present in the map, it means this is a new folder name and no modifications are needed, so it's added to the map and to the result.

This solution is quite efficient and avoids unnecessary computations through the use of hashmap. It ensures we don't create duplicate folders, and still makes efficient use of time and space.

Applying our solution to solve our problem, we create a hashmap to hold the count of each file name. For each name in the input, if it doesn't exist in the map, we add it to the map and set its count to 1. If it already exists, we increment the count until we find a name not in the map, which we then add to the map. Finally, we return a list or an array of all the folder names.

All the solutions have a time complexity of O(N), where N is the size of the input array. They iterate over the input array once. The space complexity is also O(N), due to the space used by the map to hold the count of the file names.

These Python, Java, and JavaScript solutions are easy to understand and write. They offer an intuitive way to solve this problem, by focusing on using hashing to keep track of created folder names and their counts. Each solution also includes loops to handle edge cases of existing names, ensuring unique folder names without neglecting any input name.