Code Implementation

class Solution:
    def getFolderNames(self, names):
        name_count = {}
        result = []
        for name in names:
            if name not in name_count:
                result.append(name)
                name_count[name] = 1
            else:
                k = name_count[name]
                new_name = f"{name}({k})"
                while new_name in name_count:
                    k += 1
                    new_name = f"{name}({k})"
                result.append(new_name)
                name_count[name] = k + 1
                name_count[new_name] = 1
        return result
      

class Solution {
public:
    vector<string> getFolderNames(vector<string>& names) {
        unordered_map<string, int> nameCount;
        vector<string> result;
        for (const string& name : names) {
            if (nameCount.find(name) == nameCount.end()) {
                result.push_back(name);
                nameCount[name] = 1;
            } else {
                int k = nameCount[name];
                string newName;
                do {
                    newName = name + "(" + to_string(k) + ")";
                    ++k;
                } while (nameCount.find(newName) != nameCount.end());
                result.push_back(newName);
                nameCount[name] = k;
                nameCount[newName] = 1;
            }
        }
        return result;
    }
};
      

class Solution {
    public String[] getFolderNames(String[] names) {
        Map<String, Integer> nameCount = new HashMap<>();
        String[] result = new String[names.length];
        for (int i = 0; i < names.length; ++i) {
            String name = names[i];
            if (!nameCount.containsKey(name)) {
                result[i] = name;
                nameCount.put(name, 1);
            } else {
                int k = nameCount.get(name);
                String newName = name + "(" + k + ")";
                while (nameCount.containsKey(newName)) {
                    k++;
                    newName = name + "(" + k + ")";
                }
                result[i] = newName;
                nameCount.put(name, k + 1);
                nameCount.put(newName, 1);
            }
        }
        return result;
    }
}
      

var getFolderNames = function(names) {
    const nameCount = {};
    const result = [];
    for (let name of names) {
        if (!(name in nameCount)) {
            result.push(name);
            nameCount[name] = 1;
        } else {
            let k = nameCount[name];
            let newName = `${name}(${k})`;
            while (newName in nameCount) {
                k += 1;
                newName = `${name}(${k})`;
            }
            result.push(newName);
            nameCount[name] = k + 1;
            nameCount[newName] = 1;
        }
    }
    return result;
};
      

Problem Description

You are given an array of strings names representing file names to be saved in a folder. If a file name already exists in the folder, you must create a new name by appending a suffix in the format (k), where k is the smallest positive integer such that the new name does not exist in the folder. Each time you append a suffix, you must ensure that the resulting name is also unique. Return an array of the actual names assigned to each file, in order.

• Each name in names must be used in order.
• Once a name (or suffixed name) is assigned, it cannot be reused.
• There is always a solution for any input.

Thought Process

At first glance, the problem seems straightforward: just check if a name already exists, and if so, add a suffix. However, as names and their suffixed versions can themselves be duplicated, we need to track all previously used names efficiently.

A brute-force approach would be to, for each incoming name, repeatedly check if the candidate name exists in the list of used names, incrementing k until we find an unused one. But as the number of files grows, this would be slow.

To optimize, we realize we can use a hash map (dictionary) to record the next suffix k to try for each base name, and to quickly check if any candidate name is already used. This lets us generate unique names in constant time per operation, avoiding unnecessary repeated checks.

Solution Approach

• Step 1: Create a hash map (dictionary) called nameCount to record the next suffix number to use for each base name, and to track all assigned names.
• Step 2: Iterate through the names array:
  • If the current name is not in nameCount, it means it is unique so far. Assign it as-is, add to the result, and set nameCount[name] = 1 (the next suffix to use if needed).
  • If name is already in nameCount, repeatedly generate new names by appending (k) where k is the current value for that base name, and increment k until a unique name is found (i.e., not in nameCount).
  • Once a unique name is found, add it to the result, update nameCount for both the base name and the new name. For the base name, set the next suffix to try, and for the new name, initialize its count to 1.
• Step 3: Return the list of assigned file names.

We use a hash map because it allows for O(1) lookups and updates, making the algorithm efficient even for large input sizes.

Example Walkthrough

Let's use the input ["gta","gta(1)","gta","avalon"].

1. The first name is "gta" — it's not used yet. Assign as-is: ["gta"]. nameCount = {"gta": 1}
2. Next is "gta(1)" — also new. Assign as-is: ["gta", "gta(1)"]. nameCount = {"gta": 1, "gta(1)": 1}
3. Next is "gta" again. It's been used, so try "gta(1)" — but that's used too. Try "gta(2)" — unused. Assign: ["gta", "gta(1)", "gta(2)"]. nameCount = {"gta": 3, "gta(1)": 1, "gta(2)": 1}
4. Last is "avalon" — new. Assign as-is: ["gta", "gta(1)", "gta(2)", "avalon"].

Each step ensures uniqueness, even when names with suffixes are present in the input.

Time and Space Complexity

• Brute-force approach: For each name, you might have to scan all previous names to check for uniqueness, leading to O(N^2) time for N files.
• Optimized approach (with hash map): Each name lookup and update in the hash map is O(1), so the overall time complexity is O(N), where N is the number of input names. In the worst case, there may be some extra iterations for suffixes, but overall it's very efficient.
• Space complexity: O(N) for storing the result and the hash map.

Summary

This problem is elegantly solved by using a hash map to track both used names and the next suffix to try for each base name. The key insight is to avoid repeated scanning by leveraging constant-time lookups, allowing us to efficiently generate unique file names even with complex input patterns. This approach is both simple and highly effective, scaling gracefully with input size.