In the Windows filesystem, two folders/files cannot have the same name. If you enter a folder name that was previously used, the system will have a suffix addition to its name in the form of (k), where, k is the smallest positive integer such that the obtained name remains unique.
Problem Statement
Given an array of strings dirNames of size n. You will create n folders in your windows file system such that, at the ith minute, you will create a folder with the name dirNames[i]. The task is to return an array of strings of length n where ans[i] is the actual name the system will assign to the ith folder when you create it.
Examples:
Input: dirNames = ["abc","pqrs","mnp","abc(2019)"] Output: ["abc","pqrs","mnp","abc(2019)"]
Explanation: Let’s see how the file system creates folder names:
“abc” –> not assigned before, remains “abc”
“pqrs” –> not assigned before, remains “pqrs”
“mnp” –> not assigned before, remains “mnp”
“abc(2019)” –> not assigned before, remains “abc(2019)”
Input: dirNames = ["cod","cod(1)","cod","test"] Output: ["cod","cod(1)","cod(2)","test"]
Explanation: Let’s see how the file system creates folder names:
“cod” –> not assigned before, remains “cod”
“cod(1)” –> not assigned before, remains “cod(1)”
“cod” –> the name is reserved, system adds (k), since “cod(1)” is also reserved, systems put k = 2. it becomes “cod(2)”
“test” –> not assigned before, remains “test”
Solution
We will maintain a map to store whether the particular name occurs how many times already. Then iteratively check if the name already came and it contains the number in brackets. Then increase the number until that didn’t exist. In the meanwhile, update the map too.
Java
import java.io.*;import java.util.*; public class GFG { // Main Method public static void main(String[] args) throws IOException { String[] dirNames = { "cod", "cod(1)", "cod", "test" }; String[] output = getFolderNames(dirNames); for (String i : output) { System.out.print(i + " "); } } public static String[] getFolderNames(String[] names) { Map<String, Integer> m = new HashMap<>(); for (int i = 0; i < names.length; m.put(names[i], 1), i++) if (m.containsKey(names[i])) { int k = m.get(names[i]); while ( m.containsKey(names[i] + "(" + k + ")")) k++; m.put(names[i], k + 1); names[i] = names[i] + "(" + k + ")"; } return names; }} |
Output:
cod cod(1) cod(2) test
- Time Complexity: O(n)
- Space Complexity: O(n2)
