Day 32 of Studying LeetCode Solution until I Can Solve One on My Own: Problem#1487. Making File Names Unique(Med/JS)
Published: 2022-03-19 02:14:58

**Intro:** I am a former accountant turned software engineer graduated from coding bootcamp. Algorithms and Data Structure is an unavoidable part of interviews for most of the tech companies now. And one of my friends told me that you need to solve a medium leetcode problem under 60 seconds in order to get into the top tech companies.So I thought I'd start learning how to do it while job searching.

Since I have no clue on how to solve any of the problems (even the easy ones), I thought there is no point for me to waste hours and can't get it figured out. **Here is my approach:**
- Pick a leetcode problem randomly or Online Assessment from targeted companies.
- Study 1-2 solutions from Youtube or LeetCode discussion section. One brute force solution, another one more optimal.
- Write a blog post with detailed explanation and do a verbal walk through to help understand the solutions better.
- Code out the solution in LeetCode without looking at the solutions
- **Combat the forgetting curve:** Re-do the question for the next three days. And come back regularly to revisit the problem.

******************************************

**1487. Making File Names Unique**
`Difficulty: Medium` `Language: JavaScript` 

<!--Expedia Interview-->

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.

******************************************

**Solution:**
1. Keep a map of each name and the smallest valid integer that can be appended as a suffix to it.
2. If the name is not present in the map, you can use it without adding any suffixes.
3. If the name is present in the map, append the smallest proper suffix, and add the new name to the map.

```
 var getFolderNames = function(names) {
    
    const folders = {}, counters = {}; const ans = [];

//initial three variables to respectively store name of the
//folder, count of each name if duplicated and final answer array 

    for(let i = 0; i < names.length; i++) {

//Loop through each name in the given array

        const name = names[i];
        let folderName = name, num = counters[name] || 1;

//if the ith name in the 'names' array is seen in 'counters', then
//assign it's value to num, otherwise num = 1.

        while(folders[folderName] !== undefined) {

//if the ith name in the 'names' array is seen in 'folders'

            folderName = `${name}(${num++})`;

//update folder name to the original name + number of time
//appeared

        }
        folders[folderName] = i;

//if the ith name in the 'names' array is NOT seen in 'folders',
//assign i as it's value.

        counters[name] = num;

//if the ith name in the 'names' array is NOT seen in 'counters',
//assign num as it's value.

        ans.push(folderName);

//Push updated folder name in the answer array

    }

    return ans;
};
```
Time Complexity: O(n)
Space Complexity: O(n)

******************************************

**References:**
[LeetCode Problem Link](https://leetcode.com/problems/making-file-names-unique/)
[LeetCode Discussion: _savely] (https://leetcode.com/problems/making-file-names-unique/discuss/1372015/Javascript-172ms-two-hashmaps-O(n)-time-O(n)-space)
[Blog Cover Image Credit](https://www.istockphoto.com/portfolio/monsitj?mediatype=photography)