Leetcode 1487: Making File Names Unique
You are given an array ’names’ where each element represents a folder name. You will create folders sequentially at each minute. If a folder with the same name already exists, a suffix of the form ‘(k)’ is added, where k is the smallest positive integer such that the resulting name is unique.
Problem
Approach
Steps
Complexity
Input: An array of strings 'names' of size n, where each string represents a folder name.
Example: names = ["doc", "doc", "img", "doc(1)"]
Constraints:
• 1 <= names.length <= 5 * 10^4
• 1 <= names[i].length <= 20
• names[i] consists of lowercase English letters, digits, and/or round brackets.
Output: Return an array of strings where each string is the folder name assigned by the system after the respective minute.
Example: Output: ["doc", "doc(1)", "img", "doc(1)(1)"]
Constraints:
• The returned list must contain n strings, one for each folder name assigned.
Goal: Create folder names in such a way that they are unique by appending the smallest integer k to the name if necessary.
Steps:
• 1. Initialize a dictionary to track the frequency of folder names.
• 2. Iterate over the 'names' array.
• 3. If the folder name is already in the dictionary, append '(k)' where k is the smallest integer that makes the name unique.
• 4. Update the dictionary with the new name and continue.
Goal: Handle all edge cases where folder names repeat or when the list is very large.
Steps:
• The input size can be large, so the solution must be efficient.
• The folder names can include digits and brackets.
Assumptions:
• The folder names are case-sensitive.
• The suffix '(k)' is always appended to the original name in case of a conflict.
• Input: names = ["doc", "doc", "img", "doc(1)"]
• Explanation: The first 'doc' is assigned as 'doc', the second 'doc' gets a suffix '(1)', and so on.
• Input: names = ["file", "file", "file", "image"]
• Explanation: The first 'file' is assigned as 'file', the second gets '(1)', the third gets '(2)', and 'image' remains 'image'.
Approach: To ensure that folder names are unique, a dictionary is used to track existing names and their frequencies. Whenever a conflict occurs, the smallest integer suffix is added to the name.
Observations:
• Using a dictionary to track folder names will help in efficiently checking for conflicts.
• The system needs to append the smallest valid suffix (k) for names that conflict, which can be achieved by incrementing the counter for each name.
Steps:
• 1. Create a map to store the frequency of each folder name.
• 2. For each name in the input list, check if it exists in the map.
• 3. If it exists, append a suffix and keep checking until a unique name is found.
• 4. Update the map and continue.
Empty Inputs:
• If the input list is empty, the output should also be empty.
Large Inputs:
• Handle cases where the number of folders is close to the upper limit (50,000).
Special Values:
• Names that include digits or brackets should be processed correctly.
Constraints:
• Ensure the solution is efficient enough to handle the maximum input size.
vector<string> getFolderNames(vector<string>& names) {
map<string, int> mp;
for(int i = 0; i < names.size(); i++) {
if(mp.count(names[i])) {
int k = mp[names[i]];
while(mp.count(names[i] + "(" + to_string(k) + ")")) {
k++;
mp[names[i]]++;
}
mp[names[i]]++;
names[i] = names[i] + "(" + to_string(k) + ")";
}
mp[names[i]] = 1;
}
return names;
}
1 : Method
vector<string> getFolderNames(vector<string>& names) {
The function starts by accepting a vector of strings, `names`, which contains the folder names. It will modify this vector to ensure all names are unique.
2 : Variable Initialization
map<string, int> mp;
A map `mp` is initialized to keep track of how many times each folder name appears. The key is the folder name, and the value is the number of times it has been encountered.
3 : Loop
for(int i = 0; i < names.size(); i++) {
This loop iterates over each folder name in the `names` vector to process it and ensure uniqueness.
4 : Condition
if(mp.count(names[i])) {
If the current folder name already exists in the map (`mp`), we need to modify the name to make it unique.
5 : Variable Initialization
int k = mp[names[i]];
The variable `k` is initialized to the current count of the folder name in the map. This will be used to append a unique number to the name.
6 : Loop
while(mp.count(names[i] + "(" + to_string(k) + ")")) {
This while loop checks if the current name with an appended `(k)` already exists in the map. If it does, we increment `k` to try a higher number.
7 : Variable Increment
k++;
Increment `k` to try the next possible number in the sequence for the modified folder name.
8 : Map Update
mp[names[i]]++;
Update the map to increment the count of the original folder name, indicating that we're trying a new modified version of it.
9 : Map Update
mp[names[i]]++;
After finding a unique name, increment the count of the original folder name in the map.
10 : Modify Name
names[i] = names[i] + "(" + to_string(k) + ")";
The current folder name is updated by appending `(k)` to it, where `k` is the number that ensures the name is unique.
11 : Map Update
mp[names[i]] = 1;
If the folder name is new (not encountered before), initialize its count in the map to `1`.
12 : Return
return names;
Finally, return the modified vector `names`, which now contains unique folder names.
Best Case: O(1) for each folder if no conflicts occur.
Average Case: O(n) where n is the number of folders.
Worst Case: O(n * k) where k is the number of suffixes added in the worst case.
Description: The worst case occurs when many folder names conflict, requiring checking multiple suffixes.
Best Case: O(n) as we need to store the result array.
Worst Case: O(n) for the space used by the dictionary storing the folder names.
Description: The space complexity is proportional to the number of unique folder names.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus