LeetCode 1487 - Making File Names Unique

The problem asks us to simulate how a file system assigns folder names when duplicate names appear. We are given an array names, where names[i] represents the folder name requested at the i-th minute. The file system must ensure that every created folder has a unique name.

leetcodemediumarrayhash-tablestring

LeetCode Problem 1487

Difficulty: 🟡 Medium
Topics: Array, Hash Table, String

Solution

Problem Understanding

The problem asks us to simulate how a file system assigns folder names when duplicate names appear.

We are given an array names, where names[i] represents the folder name requested at the i-th minute. The file system must ensure that every created folder has a unique name.

If a requested name has never been used before, the system accepts it directly. However, if the name already exists, the system appends a suffix in the format (k) where k is the smallest positive integer that produces a unique name.

For example, if "gta" already exists:

  • The system first tries "gta(1)"
  • If that also exists, it tries "gta(2)"
  • It continues increasing k until it finds an unused name

The output should contain the actual assigned folder names after resolving all conflicts.

The constraints are important:

  • names.length can be as large as 5 * 10^4
  • Each string length is at most 20

A quadratic solution would be too slow for the upper limit. Since many names can repeat, we need a way to quickly determine both whether a name exists and what suffix to try next.

Several edge cases are especially important:

  • Repeated identical names such as ["a", "a", "a", "a"]
  • Names that already contain suffixes like "gta(1)"
  • Interleaving names where suffixes become occupied before duplicates occur
  • Cases where many suffixes are already taken, forcing the algorithm to skip multiple values efficiently

The problem guarantees that all names only contain lowercase English letters, digits, and parentheses, so we do not need to validate formatting.

Approaches

Brute Force Approach

The most straightforward solution is to maintain a set of used names.

For each incoming name:

  • If it is unused, insert it into the set
  • Otherwise, start with k = 1
  • Repeatedly generate name + "(" + k + ")" until an unused name is found
  • Insert the new unique name into the set

This approach is correct because it directly follows the rules described in the problem statement.

However, it can become very slow. Suppose we repeatedly insert "a" many times. Every insertion restarts checking from k = 1, even though we already know smaller suffixes are occupied.

For example:

"a"
"a(1)"
"a(2)"
"a(3)"
...

When inserting another "a", the brute force solution may scan through many previously used suffixes again.

In the worst case, this leads to quadratic behavior.

Optimal Approach

The key insight is that we should remember the next suffix to try for every base name.

Instead of restarting from 1 every time, we maintain a hash map:

name -> next available suffix

For example:

"a" -> 4

means that when "a" appears again, we should immediately start checking from suffix 4.

This optimization avoids repeated scanning of already known invalid suffixes.

We still use a hash map or set to track which names are already assigned, but now we also cache progress for each base name.

Because hash map operations are approximately O(1), the entire algorithm becomes efficient enough for the problem constraints.

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(n) Repeatedly scans suffixes from 1
Optimal O(n) average O(n) Stores next available suffix for fast lookup

Algorithm Walkthrough

  1. Create a hash map called name_count.

This map serves two purposes:

  • It tells us whether a name already exists
  • It stores the next suffix to try for a base name
  1. Create an answer array called result.

This will store the actual assigned folder names in order. 3. Iterate through each name in names.

For every requested folder name, determine whether it is already used. 4. If the name does not exist in name_count:

  • Add it directly to result
  • Store name_count[name] = 1

The value 1 means that if this base name appears again later, we should first try suffix (1). 5. If the name already exists:

  • Retrieve the next suffix candidate from name_count[name]
  • Construct a candidate name:
name(k)
  • While this candidate already exists, increment k
  • Continue until a unique candidate is found
  1. Once a unique name is discovered:
  • Append it to result
  • Mark the new name as used
  • Update name_count[name] so future searches start from the next suffix
  1. After processing all names, return result.

Why it works

The algorithm maintains the invariant that every assigned folder name is unique and recorded in the hash map.

For every base name, the stored suffix pointer always represents the smallest suffix that has not yet been confirmed invalid. This guarantees that we never skip a valid smaller suffix and never unnecessarily retry suffixes we already know are occupied.

Therefore, every generated name is both unique and minimal, exactly matching the problem requirements.

Python Solution

from typing import List

class Solution:
    def getFolderNames(self, names: List[str]) -> List[str]:
        name_count = {}
        result = []

        for name in names:
            if name not in name_count:
                result.append(name)
                name_count[name] = 1
            else:
                k = name_count[name]

                while f"{name}({k})" in name_count:
                    k += 1

                new_name = f"{name}({k})"

                result.append(new_name)

                name_count[name] = k + 1
                name_count[new_name] = 1

        return result

The implementation uses a single dictionary called name_count.

When a name appears for the first time, it is inserted directly into the result array and marked in the dictionary.

When a duplicate appears, the algorithm retrieves the next suffix to try from the dictionary. Instead of restarting from 1, it resumes from the previously stored value, which avoids redundant checks.

The while loop continues searching until a unique generated name is found. Once found, the algorithm updates both:

  • The original base name's next suffix pointer
  • The generated unique name itself

This ensures all future operations remain efficient.

Go Solution

package main

import "fmt"

func getFolderNames(names []string) []string {
	nameCount := make(map[string]int)
	result := make([]string, 0, len(names))

	for _, name := range names {
		if _, exists := nameCount[name]; !exists {
			result = append(result, name)
			nameCount[name] = 1
		} else {
			k := nameCount[name]

			for {
				newName := fmt.Sprintf("%s(%d)", name, k)

				if _, exists := nameCount[newName]; !exists {
					result = append(result, newName)

					nameCount[name] = k + 1
					nameCount[newName] = 1

					break
				}

				k++
			}
		}
	}

	return result
}

The Go solution follows the same logic as the Python implementation.

Go does not have Python-style f-strings, so fmt.Sprintf is used to construct suffixed names.

The hash map is implemented using map[string]int. Existence checks use the standard Go idiom:

value, exists := map[key]

Slices are dynamically appended to store the result.

There are no integer overflow concerns because suffix values remain within practical bounds for the input size constraints.

Worked Examples

Example 1

Input:

["pes","fifa","gta","pes(2019)"]

Processing steps:

Step Incoming Name Action Result Hash Map State
1 "pes" New name ["pes"] {"pes": 1}
2 "fifa" New name ["pes", "fifa"] {"pes": 1, "fifa": 1}
3 "gta" New name ["pes", "fifa", "gta"] {"pes": 1, "fifa": 1, "gta": 1}
4 "pes(2019)" New name ["pes", "fifa", "gta", "pes(2019)"] {"pes": 1, "fifa": 1, "gta": 1, "pes(2019)": 1}

Final output:

["pes","fifa","gta","pes(2019)"]

Example 2

Input:

["gta","gta(1)","gta","avalon"]

Processing steps:

Step Incoming Name Action Result Hash Map State
1 "gta" New name ["gta"] {"gta": 1}
2 "gta(1)" New name ["gta", "gta(1)"] {"gta": 1, "gta(1)": 1}
3 "gta" Duplicate, try "gta(1)" then "gta(2)" ["gta", "gta(1)", "gta(2)"] {"gta": 3, "gta(1)": 1, "gta(2)": 1}
4 "avalon" New name ["gta", "gta(1)", "gta(2)", "avalon"] {"gta": 3, "gta(1)": 1, "gta(2)": 1, "avalon": 1}

Final output:

["gta","gta(1)","gta(2)","avalon"]

Example 3

Input:

["onepiece","onepiece(1)","onepiece(2)","onepiece(3)","onepiece"]

Processing steps:

Step Incoming Name Action Result Hash Map State
1 "onepiece" New name ["onepiece"] {"onepiece": 1}
2 "onepiece(1)" New name ["onepiece", "onepiece(1)"] {"onepiece": 1, "onepiece(1)": 1}
3 "onepiece(2)" New name ["onepiece", "onepiece(1)", "onepiece(2)"] {"onepiece": 1, "onepiece(1)": 1, "onepiece(2)": 1}
4 "onepiece(3)" New name ["onepiece", "onepiece(1)", "onepiece(2)", "onepiece(3)"] {"onepiece": 1, "onepiece(1)": 1, "onepiece(2)": 1, "onepiece(3)": 1}
5 "onepiece" Duplicate, tries 1,2,3 then uses 4 ["onepiece", "onepiece(1)", "onepiece(2)", "onepiece(3)", "onepiece(4)"] {"onepiece": 5, "onepiece(1)": 1, "onepiece(2)": 1, "onepiece(3)": 1, "onepiece(4)": 1}

Final output:

["onepiece","onepiece(1)","onepiece(2)","onepiece(3)","onepiece(4)"]

Complexity Analysis

Measure Complexity Explanation
Time O(n) average Each name and suffix is processed efficiently using hash map lookups
Space O(n) The hash map stores all assigned names

Although the algorithm contains a while loop, the suffix pointer optimization ensures we do not repeatedly scan from the beginning. Each generated suffix progresses forward, making the total work across all iterations effectively linear on average.

Test Cases

from typing import List

class Solution:
    def getFolderNames(self, names: List[str]) -> List[str]:
        name_count = {}
        result = []

        for name in names:
            if name not in name_count:
                result.append(name)
                name_count[name] = 1
            else:
                k = name_count[name]

                while f"{name}({k})" in name_count:
                    k += 1

                new_name = f"{name}({k})"

                result.append(new_name)

                name_count[name] = k + 1
                name_count[new_name] = 1

        return result

sol = Solution()

# Example 1
assert sol.getFolderNames(
    ["pes","fifa","gta","pes(2019)"]
) == ["pes","fifa","gta","pes(2019)"]  # no duplicates

# Example 2
assert sol.getFolderNames(
    ["gta","gta(1)","gta","avalon"]
) == ["gta","gta(1)","gta(2)","avalon"]  # suffix collision

# Example 3
assert sol.getFolderNames(
    ["onepiece","onepiece(1)","onepiece(2)","onepiece(3)","onepiece"]
) == ["onepiece","onepiece(1)","onepiece(2)","onepiece(3)","onepiece(4)"]  # multiple occupied suffixes

# Single element
assert sol.getFolderNames(
    ["a"]
) == ["a"]  # minimal input

# Repeated same name
assert sol.getFolderNames(
    ["a", "a", "a", "a"]
) == ["a", "a(1)", "a(2)", "a(3)"]  # repeated duplicates

# Existing suffixed names
assert sol.getFolderNames(
    ["doc", "doc(1)", "doc", "doc(1)", "doc"]
) == ["doc", "doc(1)", "doc(2)", "doc(1)(1)", "doc(3)"]  # nested suffix handling

# Already complex names
assert sol.getFolderNames(
    ["x(1)", "x(1)", "x(1)(1)"]
) == ["x(1)", "x(1)(1)", "x(1)(1)(1)"]  # parentheses treated as normal characters

# Large chain
assert sol.getFolderNames(
    ["a"] * 6
) == ["a", "a(1)", "a(2)", "a(3)", "a(4)", "a(5)"]  # stress repeated generation

# Mixed independent names
assert sol.getFolderNames(
    ["a", "b", "a", "b", "a"]
) == ["a", "b", "a(1)", "b(1)", "a(2)"]  # independent counters

print("All tests passed.")
Test Why
["pes","fifa","gta","pes(2019)"] Verifies no unnecessary renaming
["gta","gta(1)","gta","avalon"] Verifies suffix skipping
["onepiece","onepiece(1)",...] Verifies multiple occupied suffixes
["a"] Validates minimum input
["a","a","a","a"] Tests repeated duplicates
["doc","doc(1)","doc",...] Tests nested suffix generation
["x(1)","x(1)",...] Ensures parentheses are treated normally
["a"] * 6 Stress test for repeated insertions
["a","b","a","b","a"] Tests independent name tracking

Edge Cases

One important edge case occurs when names already contain parentheses, such as "gta(1)". A naive implementation might try to parse this as a base name plus suffix. However, the problem treats every string literally. "gta(1)" is simply another folder name. The implementation correctly handles this because it never attempts to parse or normalize names. Every string is stored exactly as received.

Another tricky case is repeated duplicates like:

["a", "a", "a", "a", "a"]

Without optimization, the algorithm would repeatedly retry suffixes from (1) onward for every duplicate, leading to quadratic performance. The hash map optimization avoids this by remembering the next available suffix for "a".

A third important edge case happens when suffixed names already exist before duplicates appear:

["doc", "doc(1)", "doc"]

When the second "doc" appears, the algorithm must skip "doc(1)" and generate "doc(2)". The implementation handles this correctly because every generated or original name is inserted into the same hash map, allowing collision checks against both original names and previously generated names.