# Making File Names Unique
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/making-file-names-unique)
Canonical: https://scaleengineer.com/dsa/problems/making-file-names-unique
**Data structures:** Array, Hash Table, String
---
## Problem
Given an array of strings `names` of size `n`. You will create `n` folders in your file system **such that**, at the `ith` 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 `ith` 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 * 104`
* `1 <= names[i].length <= 20`
* `names[i]` consists of lowercase English letters, digits, and/or round brackets.

# Approaches
## Brute Force with Hash Set
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.
**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.
**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)`.
### Explanation
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.

```java
import java.util.HashSet;
import java.util.Set;

class Solution {
    public String[] getFolderNames(String[] names) {
        Set<String> seen = new HashSet<>();
        String[] result = new String[names.length];
        
        for (int i = 0; i < names.length; i++) {
            String name = names[i];
            if (!seen.contains(name)) {
                result[i] = name;
                seen.add(name);
            } else {
                int k = 1;
                String newName = name + "(" + k + ")";
                while (seen.contains(newName)) {
                    k++;
                    newName = name + "(" + k + ")";
                }
                result[i] = newName;
                seen.add(newName);
            }
        }
        return result;
    }
}
```
### Algorithm
- 1. Initialize a `HashSet<String>` `seen` to store unique folder names.
- 2. Initialize a `String[]` `result` of the same size as `names`.
- 3. Iterate through each `name` in the `names` array with index `i`.
- 4. If `name` is not in `seen`:
  - a. Add `name` to `seen`.
  - b. Set `result[i] = name`.
- 5. 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`.
- 6. Return the `result` array.

## Optimized Approach with Hash Map
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.
**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.
**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.
### Explanation
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.

```java
import java.util.HashMap;
import java.util.Map;

class Solution {
    public String[] getFolderNames(String[] names) {
        Map<String, Integer> nameToCount = new HashMap<>();
        String[] result = new String[names.length];
        
        for (int i = 0; i < names.length; i++) {
            String name = names[i];
            if (nameToCount.containsKey(name)) {
                int k = nameToCount.get(name);
                String newName = name + "(" + k + ")";
                while (nameToCount.containsKey(newName)) {
                    k++;
                    newName = name + "(" + k + ")";
                }
                nameToCount.put(name, k + 1);
                nameToCount.put(newName, 1);
                result[i] = newName;
            } else {
                nameToCount.put(name, 1);
                result[i] = name;
            }
        }
        return result;
    }
}
```
### Algorithm
- 1. Initialize a `HashMap<String, Integer>` `nameToCount` to store the next available suffix for each name.
- 2. Initialize a `String[]` `result` of the same size as `names`.
- 3. Iterate through each `name` in the `names` array with index `i`.
- 4. 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)`.
- 5. 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)`.
- 6. Return the `result` array.

# Solutions
### Java

```java
class 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 ; } }
```

### CPP

```cpp
class 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 ; } };
```

### Python

```python
class 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
```