Making File Names Unique

Med

#1372Time: `O(N^2 * L)` in the worst case, where `N` is the number of names and `L` is the maximum length of a name. The worst case occurs for an input like `["a", "a", "a", ..., "a"]`. For the `i`-th "a", we might have to check `a(1), a(2), ..., a(i-1)`, leading to `O(i)` probes. The total number of probes would be `sum(i for i=0 to N-1) = O(N^2)`. Each probe involves string creation and hashing, taking `O(L)` time.Space: `O(N * L)` to store the `seen` set and the `result` array, where `N` is the number of names and `L` is their average length.

Data structures

Array Hash Table String

Prompt

Given an array of strings names of size n. You will create n folders in your file system such that, at the i^th 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 i^th 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 * 10⁴
1 <= names[i].length <= 20
names[i] consists of lowercase English letters, digits, and/or round brackets.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach iterates through the given names array. For each name, it checks if a unique version of it has already been generated. A hash set is used to keep track of all the unique names assigned so far. If the current name is already in the hash set, it tries to create a new unique name by appending a suffix (k), starting with k=1. It increments k and checks for the uniqueness of the new name name(k) until an unused name is found.

Algorithm

1. Initialize a HashSet<String> seen to store unique folder names.
1. Initialize a String[] result of the same size as names.
1. Iterate through each name in the names array with index i.
1. If name is not in seen:
- a. Add name to seen.
- b. Set result[i] = name.
1. If name is already in seen:
- a. Initialize an integer k = 1.
- b. Create a newName by appending (k) to name.
- c. While newName exists in seen:
  - i. Increment k.
  - ii. Update newName with the new k.
- d. Add the final unique newName to seen.
- e. Set result[i] = newName.
1. Return the result array.

Walkthrough

We use a HashSet<String> called seen to store all the file names that have been created. We iterate through the input names array one by one. For each name, we check if it's present in seen. If name is not in seen, it's unique. We add it to seen and to our result array. If name is already in seen, we need to find a modification. We start a counter k from 1. In a loop, we construct a newName as name + "(" + k + ")". We check if this newName is in seen. If it is, we increment k and repeat. If not, we've found a unique name. We add this newName to seen and our result array, then move to the next name in the input. The main drawback is that for a repeated name, we always start searching for the suffix k from 1. For example, if we have processed ["a", "a", "a"] and generated ["a", "a(1)", "a(2)"], when we see the fourth "a", we will check "a(1)", then "a(2)", before trying "a(3)". This can lead to many redundant checks if a name appears frequently.

1import java.util.HashSet;2import java.util.Set;3 4class Solution {5    public String[] getFolderNames(String[] names) {6        Set<String> seen = new HashSet<>();7        String[] result = new String[names.length];8        9        for (int i = 0; i < names.length; i++) {10            String name = names[i];11            if (!seen.contains(name)) {12                result[i] = name;13                seen.add(name);14            } else {15                int k = 1;16                String newName = name + "(" + k + ")";17                while (seen.contains(newName)) {18                    k++;19                    newName = name + "(" + k + ")";20                }21                result[i] = newName;22                seen.add(newName);23            }24        }25        return result;26    }27}

Complexity

Time

`O(N^2 * L)` in the worst case, where `N` is the number of names and `L` is the maximum length of a name. The worst case occurs for an input like `["a", "a", "a", ..., "a"]`. For the `i`-th "a", we might have to check `a(1), a(2), ..., a(i-1)`, leading to `O(i)` probes. The total number of probes would be `sum(i for i=0 to N-1) = O(N^2)`. Each probe involves string creation and hashing, taking `O(L)` time.

Space

`O(N * L)` to store the `seen` set and the `result` array, where `N` is the number of names and `L` is their average length.

Trade-offs

Pros

Simple to understand and implement.
Faster than a pure brute-force approach that scans the result array every time, thanks to the O(1) average time complexity of hash set operations.

Cons

Inefficient for inputs with many repeated names. For a name that appears m times, the total number of checks to find unique versions can be on the order of 1 + 2 + ... + m-1 = O(m^2).
This can lead to a Time Limit Exceeded (TLE) error on large test cases with many collisions. The worst-case time complexity is O(N^2 * L).

This approach improves upon the previous one by using a hash map to keep track of the next available suffix for each base name. Instead of starting the search for k from 1 every time a duplicate is found, we remember the last k used for a particular name and start searching from k+1. This avoids redundant checks and significantly improves performance.

Algorithm

1. Initialize a HashMap<String, Integer> nameToCount to store the next available suffix for each name.
1. Initialize a String[] result of the same size as names.
1. Iterate through each name in the names array with index i.
1. If name is not a key in nameToCount:
- a. It's a new unique name.
- b. Set result[i] = name.
- c. Put name into the map with value 1, indicating that the next suffix to try for name is (1).
1. If name is a key in nameToCount:
- a. Retrieve the next suffix to try, k = nameToCount.get(name).
- b. Construct newName = name + "(" + k + ")".
- c. While newName is already a key in nameToCount:
  - i. Increment k.
  - ii. Update newName with the new k.
- d. We have found a unique newName. Set result[i] = newName.
- e. Update the map for the original name: nameToCount.put(name, k + 1).
- f. Add the new name to the map: nameToCount.put(newName, 1).
1. Return the result array.

Walkthrough

We use a HashMap<String, Integer> called nameToCount. For any name s that has appeared before, nameToCount.get(s) will give us the next integer suffix k to try. We iterate through the input names array. For each name: if name is not in our map, it's the first time we've seen it. We assign it as is, and record in the map that the next time we see name, we should try appending (1). So, we set nameToCount.put(name, 1). If name is already in the map, it means we've encountered it before. We retrieve its next suffix counter k from the map. We then enter a loop to find the first available unique name newName = name + "(" + k + ")". We check if this newName is in our map. If it is, it means name(k) is already taken (perhaps it was an original name in the input), so we increment k and try again. Once we find an unused newName, we assign it. We must then update our map: the original name will next need to try k+1, so we update nameToCount.put(name, k + 1). The newly created newName is now a used name. We record that if we see newName again, we should start by trying newName(1). So, we set nameToCount.put(newName, 1). This stateful tracking of the next suffix for each name avoids re-computation and makes the process much more efficient.

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

Complexity

Time

Amortized `O(N * L)`, where `N` is the number of names and `L` is the average length of a name. Each name is processed once. For duplicates, the while loop finds the next available `k`. The key is that the `k` for any given base name only ever increases. The total number of increments of `k` across the entire execution is bounded by `N`. Therefore, each hash map lookup and string operation is performed an amortized constant number of times for each name.

Space

`O(N * L)` to store the `nameToCount` map and the `result` array, where `N` is the number of names and `L` is their average length. The map can contain up to `2N-1` entries in the worst case.

Trade-offs

Pros

Highly efficient. The use of a hash map to store the next available suffix index avoids redundant checks.
The time complexity is amortized linear with respect to the number of names and their lengths.

Cons

Slightly more complex to implement due to the need to manage the state in the hash map correctly.
Uses more memory than the naive approach if many unique names are generated, as each generated name also gets an entry in the map.

Solutions

Solution

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

1class Solution { public: vector < string > getFolderNames ( vector < string >& names ) { unordered_map < string , int > d ; for ( auto & name : names ) { int k = d [ name ]; if ( k ) { while ( d [ name + "(" + to_string ( k ) + ")" ]) { k ++ ; } d [ name ] = k ; name += "(" + to_string ( k ) + ")" ; } d [ name ] = 1 ; } return names ; } };

1class Solution : def getFolderNames ( self , names : List [ str ]) -> List [ str ]: d = defaultdict ( int ) for i , name in enumerate ( names ): if name in d : k = d [ name ] while f ' { name } ( { k } )' in d : k += 1 d [ name ] = k + 1 names [ i ] = f ' { name } ( { k } )' d [ names [ i ]] = 1 return names

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem