Skip to content

1487. Making File Names Unique

Description

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.

Solutions

Solution 1: Hash Table

We can use a hash table \(d\) to record the minimum available index for each folder name, where \(d[name] = k\) means the minimum available index for the folder \(name\) is \(k\). Initially, \(d\) is empty since there are no folders.

Next, we iterate through the folder names array. For each file name \(name\):

  • If \(name\) is already in \(d\), it means the folder \(name\) already exists, and we need to find a new folder name. We can keep trying \(name(k)\), where \(k\) starts from \(d[name]\), until we find a folder name \(name(k)\) that does not exist in \(d\). We add \(name(k)\) to \(d\), update \(d[name]\) to \(k + 1\), and then update \(name\) to \(name(k)\).
  • If \(name\) is not in \(d\), we can directly add \(name\) to \(d\) and set \(d[name]\) to \(1\).
  • Then, we add \(name\) to the answer array and continue to the next file name.

After traversing all file names, we obtain the answer array.

In the code implementation below, we directly modify the \(names\) array without using an extra answer array.

The complexity is \(O(L)\), and the space complexity is \(O(L)\), where \(L\) is the sum of the lengths of all file names in the \(names\) array.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
func getFolderNames(names []string) []string {
 d := map[string]int{}
 for i, name := range names {
  if k, ok := d[name]; ok {
   for {
    newName := fmt.Sprintf("%s(%d)", name, k)
    if d[newName] == 0 {
     d[name] = k + 1
     names[i] = newName
     break
    }
    k++
   }
  }
  d[names[i]] = 1
 }
 return names
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
function getFolderNames(names: string[]): string[] {
    let d: Map<string, number> = new Map();
    for (let i = 0; i < names.length; ++i) {
        if (d.has(names[i])) {
            let k: number = d.get(names[i]) || 0;
            while (d.has(names[i] + '(' + k + ')')) {
                ++k;
            }
            d.set(names[i], k);
            names[i] += '(' + k + ')';
        }
        d.set(names[i], 1);
    }
    return names;
}

Comments