MediumNo. 1487
Making File Names Unique — LeetCode 1487 Python Solution
- Pattern
- Hash Map
- Topics
- Array, Hash Table, String
- Reading time
- 2 min
- Source
- leetcode.com
The problem
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].
Example
- Input
- names = ["pes","fifa","gta","pes(2019)"]
- Output
- ["pes","fifa","gta","pes(2019)"]
- Explanation
- Let's see how the file system creates folder names:
Python solution
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 namesComplexity
- Time
- O(n)
- Space · auxiliary
- O(L)where L is the sum of the lengths of all file names in the names array
Pattern: Hash Map
Trade memory for time: remember what you have seen so the second pass never happens. LeetCode 1487. Making File Names Unique is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Hash Table.
The hash map guide has the Python template for the pattern and the 709 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0049 | Group Anagrams | Medium |
| 0139 | Word Break | Medium |
| 0140 | Word Break II | Hard |
| 0336 | Palindrome Pairs | Hard |
| 0500 | Keyboard Row | Easy |
| 0522 | Longest Uncommon Subsequence II | Medium |
Frequently asked questions
- How hard is LeetCode 1487. Making File Names Unique?
LeetCode 1487. Making File Names Unique is rated Medium on LeetCode.
- What is the time complexity of LeetCode 1487. Making File Names Unique?
The Python solution on this page runs in O(n).
- What is the space complexity of LeetCode 1487. Making File Names Unique?
The Python solution on this page uses O(L), where L is the sum of the lengths of all file names in the names array auxiliary space.
- What topics does LeetCode 1487. Making File Names Unique cover?
LeetCode 1487. Making File Names Unique is tagged Array, Hash Table and String on LeetCode.