Making File Names Unique — Solution in Python, Java & C++
Making File Names Unique solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Making File Names Unique is a medium coding problem on arrays, strings and hash table, asked in Amazon and Microsoft interviews.
- Difficulty: Medium
- Topics: Arrays, Strings, Hash Table
- Asked at: Amazon, Microsoft
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You create n folders one after another; the i-th should be called names[i].
No two folders may share a name. When the requested name is already taken, the system appends a suffix (k), using the smallest positive integer k for which name(k) is still free.
Return the names the system actually assigns, in creation order.
Example 1
Input: names = ["doc","doc","doc(1)","doc"]
Output: ["doc","doc(1)","doc(1)(1)","doc(2)"]
Explanation: The second `doc` becomes `doc(1)`. Then `doc(1)` is taken, so the third folder becomes `doc(1)(1)`. The last `doc` finds `doc(1)` taken and settles on `doc(2)`.
Example 2
Input: names = ["gta","gta(1)","gta","avalon"]
Output: ["gta","gta(1)","gta(2)","avalon"]
Explanation: `gta(1)` was requested directly, so the repeated `gta` skips to `gta(2)`.
Example 3
Input: names = ["pes","fifa","pes(2019)"]
Output: ["pes","fifa","pes(2019)"]
Explanation: No name repeats, so nothing changes.
Constraints
1 <= names.length <= 5 * 10^41 <= names[i].length <= 20names[i] holds lowercase English letters, digits and round brackets
Hints for Making File Names Unique
Hint 1
Keep every name assigned so far in a hash set; a repeated name then needs the first free
name(k).Hint 2
Trying
k = 1, 2, 3, ...from scratch for every repeat can be quadratic when the same name repeats many times.Hint 3
Remember, per base name, the next
kworth trying. Every suffix below it is already known to be taken.
How to solve Making File Names Unique
A hash map from a name to the next suffix to try both answers "is this name taken?" and lets every repeated name resume its search where the previous one stopped.
Approach
- For each requested
name: if it is not in the map, assign it and storemap[name] = 1. - Otherwise start at
k = map[name]and increasekwhilename(k)is in the map. - Assign
name(k), setmap[name] = k + 1, and addname(k)itself to the map with value 1 (it can be requested later as a base name too).
Why it works
Suffixes below map[name] were found taken earlier, and a taken name never becomes free, so skipping them is safe and the first free k found is the smallest. Each assigned name is a new key, so the total number of failed probes is bounded by the number of names in the map.
Complexity
- Time —
O(n · L) amortised - Space —
O(n · L)
Pitfalls
- Generated names must be recorded too —
doc(1)created as a suffix blocks a later request fordoc(1). - A requested name that already contains brackets (
doc(1)) is still just a name: its own suffix is appended after it, givingdoc(1)(1).
Reference solution
Python
from typing import List
def getFolderNames(names: List[str]) -> List[str]:
nxt = {}
out = []
for name in names:
if name not in nxt:
nxt[name] = 1
out.append(name)
continue
k = nxt[name]
while f"{name}({k})" in nxt:
k += 1
got = f"{name}({k})"
nxt[name] = k + 1
nxt[got] = 1
out.append(got)
return outJava
public static String[] getFolderNames(String[] names) {
Map<String, Integer> nxt = new HashMap<>();
String[] out = new String[names.length];
for (int i = 0; i < names.length; i++) {
String name = names[i];
Integer start = nxt.get(name);
if (start == null) { nxt.put(name, 1); out[i] = name; continue; }
int k = start;
while (nxt.containsKey(name + "(" + k + ")")) k++;
String got = name + "(" + k + ")";
nxt.put(name, k + 1);
nxt.put(got, 1);
out[i] = got;
}
return out;
}C++
vector<string> getFolderNames(vector<string>& names) {
unordered_map<string, int> nxt;
vector<string> out;
for (const string& name : names) {
auto it = nxt.find(name);
if (it == nxt.end()) { nxt[name] = 1; out.push_back(name); continue; }
int k = it->second;
while (nxt.count(name + "(" + to_string(k) + ")")) k++;
string got = name + "(" + to_string(k) + ")";
nxt[name] = k + 1;
nxt[got] = 1;
out.push_back(got);
}
return out;
}JavaScript
var getFolderNames = function(names) {
var nxt = new Map();
var out = [];
for (var i = 0; i < names.length; i++) {
var name = names[i];
if (!nxt.has(name)) { nxt.set(name, 1); out.push(name); continue; }
var k = nxt.get(name);
while (nxt.has(name + '(' + k + ')')) k++;
var got = name + '(' + k + ')';
nxt.set(name, k + 1);
nxt.set(got, 1);
out.push(got);
}
return out;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.