Link to the Problem
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.
Algorithm
- For each folder name –
- If the folder name does not exist already, no need to rename the folder.
- Generate a new name by adding the suffix until we find a unique new name for the folder.
- 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. | |
| } | |
| }; |
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
