Leetcode #1487: Making File Names Unique

Link to the Problem

Making File Names Unique

Thought Process

The problem seems to be very straightforward at first. If a folder with the same name already exists, we need to add a number in front. This immediately tells us that we need to store the folders that are already present. Secondly, we need to add a number in front in case of a conflict. So each folder name should have a number associated with it. The most intuitive data structure for this is a hash map. The corner case we need to handle is that what if we append a number as a suffix and generate a suffix-ed name, say name1, and that name1 already exists as a folder name. We can handle that by ignoring that number and continue generating new names until we find a suffix with does not already exist.

Leetcode #1487: Making File Names Unique - Diagram to assist visualization, Problem Solving, Leetcode, Leetcode Solutions, Crack Coding Interview, Coding Interview, Data Structures and Algorithms
Leetcode #1487: Making File Names Unique – Diagram to assist visualization

Algorithm

  1. For each folder name –
    1. If the folder name does not exist already, no need to rename the folder.
    2. Generate a new name by adding the suffix until we find a unique new name for the folder.
    3. Increment the value associated with the final name of the folder.

Of course, detailed explanation is available in the code.

Code

class Solution {
public:
unordered_map<string, int> nameSuffix; // Folder name -> Next available value
// for the suffix.
string addSuffix(string name) {
string newName = "";
do {
newName = name + "(" + to_string(nameSuffix[name]) + ")"; // Generate a name.
nameSuffix[name]++; // Increase the count by one
} while (nameSuffix.find(newName) != nameSuffix.end()); // Until we get a used
// name for the folder.
return newName;
}
string getFolderName(string name) {
string finalName = name; // If the folder name doesn't already exist,
// no need of renaming.
if (nameSuffix.find(name) != nameSuffix.end()) { // If folder already exists -
finalName = addSuffix(name); // Add suffix to the name.
}
nameSuffix[finalName]++; // Record that the name is already in use.
return finalName; // Finally return the name for the folder.
}
vector<string> getFolderNames(vector<string>& names) {
vector<string> ans; // Hold all names of the folders after renaming.
for (auto name: names) { // For each folder name -
ans.push_back(getFolderName(name)); // Compute the name for the folder.
}
return ans; // Return answer.
}
};
view raw Leetcode_1487.cpp hosted with ❤ by GitHub

Is there anything that is still unclear? Let me know in the comments and I can elaborate further.

Don’t forget like & share the post, and subscribe to the blog to get notifications whenever solution to a new problem is added.

Happy Coding!

Similar Problems

Leetcode #388: Longest Absolute File Path



Related Posts


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s