Making File Names Unique

Medium
1786.

Making File Names Unique

Making File Names Unique is a medium coding problem on arrays, strings and hash table, asked in Amazon and Microsoft interviews.

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^4
  • 1 <= names[i].length <= 20
  • names[i] holds lowercase English letters, digits and round brackets
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string[]} names
 * @return {string[]}
 */
var getFolderNames = function(names) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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^4
  • 1 <= names[i].length <= 20
  • names[i] holds lowercase English letters, digits and round brackets

Hints for Making File Names Unique

  1. Hint 1

    Keep every name assigned so far in a hash set; a repeated name then needs the first free name(k).

  2. Hint 2

    Trying k = 1, 2, 3, ... from scratch for every repeat can be quadratic when the same name repeats many times.

  3. Hint 3

    Remember, per base name, the next k worth 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

  1. For each requested name: if it is not in the map, assign it and store map[name] = 1.
  2. Otherwise start at k = map[name] and increase k while name(k) is in the map.
  3. Assign name(k), set map[name] = k + 1, and add name(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 for doc(1).
  • A requested name that already contains brackets (doc(1)) is still just a name: its own suffix is appended after it, giving doc(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 out

Java

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.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Strings