Given an array of strings arr[] consisting of N unique directories in the form of strings, the task is to remove all the subdirectories and print the final array.
A directory S is a subdirectory if there exists any directory D such that S is the prefix of D.
Examples:
Input: arr[] = {ā/aā, ā/a/jā, ā/c/d/eā, ā/c/dā, ā/bā}
Output: { ā/aā, ā/c/dā, ā/bā}
Explanation: Directory ā/a/jā is a subdirectory of directory ā/aā, and ā/c/d/eā is a subdirectory of directory ā/c/dā.
Therefore, remove both of them.Input: arr[] = {ā/aā, ā/a/bā, ā/a/b/cā, ā/a/b/c/dā}
Output: {ā/aā}
Explanation: All directories are subdirectories of ā/aā
Naive Approach: The simplest approach is to traverse the array to check for each string, if there exists a string having it as the prefix and remove such strings from the array.Ā
Time Complexity: O(len * N2), where len is the length of the longest string in the array.
Auxiliary Space: O(N)
Efficient Approach: The idea is to sort the given array and compare the current directory at position i with the previous directory at index (i -1). If arr[i ā 1] is the prefix of arr[i] then remove arr[i]. After checking the whole array, print the remaining directories. Follow the below steps to solve the problem:
- Sort all the directories alphabetically and initialize a vector res.
- Insert the first directory into res.
- Check each directory with the last valid directory i.e., last directory from res.
- The directory is invalid(sub-directory) if it equals to some prefix of the previous valid directory. Else it is valid.
- If the current directory is valid, then add it to res.
- Print all the directories present in res after done traversing.
Below is the implementation of the above approach:
C++
// C++ program for the above approachĀ
#include <bits/stdc++.h>using namespace std;Ā
// Function to remove sub-directories// from the given lists dirvoid eraseSubdirectory(vector<string>& dir){Ā Ā Ā Ā // Store final resultĀ Ā Ā Ā vector<string> res;Ā
Ā Ā Ā Ā // Sort the given directoriesĀ Ā Ā Ā sort(dir.begin(), dir.end());Ā
Ā Ā Ā Ā // Insert 1st directoryĀ Ā Ā Ā res.push_back(dir[0]);Ā
Ā Ā Ā Ā cout << "{" << dir[0] << ", ";Ā
Ā Ā Ā Ā // Iterating in directoryĀ Ā Ā Ā for (int i = 1; i < dir.size(); i++) {Ā
Ā Ā Ā Ā Ā Ā Ā Ā // Current directoryĀ Ā Ā Ā Ā Ā Ā Ā string curr = dir[i];Ā
Ā Ā Ā Ā Ā Ā Ā Ā // Our previous valid directoryĀ Ā Ā Ā Ā Ā Ā Ā string prev = res.back();Ā
Ā Ā Ā Ā Ā Ā Ā Ā // Find length of previous directoryĀ Ā Ā Ā Ā Ā Ā Ā int l = prev.length();Ā
Ā Ā Ā Ā Ā Ā Ā Ā // If subdirectory is foundĀ Ā Ā Ā Ā Ā Ā Ā if (curr.length() > l && curr[l] == '/'Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā && prev == curr.substr(0, l))Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā continue;Ā
Ā Ā Ā Ā Ā Ā Ā Ā // Else store it in resultĀ Ā Ā Ā Ā Ā Ā Ā // valid directoryĀ Ā Ā Ā Ā Ā Ā Ā res.push_back(curr);Ā
Ā Ā Ā Ā Ā Ā Ā Ā cout << curr << ", ";Ā Ā Ā Ā }Ā
Ā Ā Ā Ā cout << "}\n";}Ā
// Driver Codeint main(){Ā Ā Ā Ā // Given lists of directories dir[]Ā Ā Ā Ā vector<string> dirĀ Ā Ā Ā Ā Ā Ā Ā = { "/a", "/a/j", "/c/d/e",Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā "/c/d", "/b" };Ā
Ā Ā Ā Ā // Function CallĀ Ā Ā Ā eraseSubdirectory(dir);Ā
Ā Ā Ā Ā return 0;} |
Java
// Java program for the above approachimport java.io.*;import java.util.*;Ā
class GFG{Ā
// Function to remove sub-directories// from the given lists dirstatic void eraseSubdirectory(ArrayList<String> dir){Ā Ā Ā Ā Ā Ā Ā Ā Ā // Store final resultĀ Ā Ā Ā ArrayList<String> res = new ArrayList<String>();Ā
Ā Ā Ā Ā // Sort the given directoriesĀ Ā Ā Ā Collections.sort(dir);Ā
Ā Ā Ā Ā // Insert 1st directoryĀ Ā Ā Ā res.add(dir.get(0));Ā
Ā Ā Ā Ā System.out.print("{" + dir.get(0) + ", ");Ā
Ā Ā Ā Ā // Iterating in directoryĀ Ā Ā Ā for(int i = 1; i < dir.size(); i++)Ā Ā Ā Ā {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // Current directoryĀ Ā Ā Ā Ā Ā Ā Ā String curr = dir.get(i);Ā
Ā Ā Ā Ā Ā Ā Ā Ā // Our previous valid directoryĀ Ā Ā Ā Ā Ā Ā Ā String prev = res.get(res.size() - 1);Ā
Ā Ā Ā Ā Ā Ā Ā Ā // Find length of previous directoryĀ Ā Ā Ā Ā Ā Ā Ā int l = prev.length();Ā
Ā Ā Ā Ā Ā Ā Ā Ā // If subdirectory is foundĀ Ā Ā Ā Ā Ā Ā Ā if (curr.length() > l &&Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā curr.charAt(l) == '/' && Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā prev.equals(curr.substring(0, l)))Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā continue;Ā
Ā Ā Ā Ā Ā Ā Ā Ā // Else store it in resultĀ Ā Ā Ā Ā Ā Ā Ā // valid directoryĀ Ā Ā Ā Ā Ā Ā Ā res.add(curr);Ā
Ā Ā Ā Ā Ā Ā Ā Ā System.out.print(curr + ", ");Ā Ā Ā Ā }Ā Ā Ā Ā System.out.print("}\n");}Ā
// Driver Codepublic static void main(String[] args){Ā Ā Ā Ā Ā Ā Ā Ā Ā // Given lists of directories dir[]Ā Ā Ā Ā ArrayList<String> dir = new ArrayList<String>(Arrays.asList(Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā "/a", "/a/j", "/c/d/e", "/c/d", "/b"));Ā
Ā Ā Ā Ā // Function CallĀ Ā Ā Ā eraseSubdirectory(dir);}}Ā
// This code is contributed by akhilsaini |
Python3
# Python3 program for the above approachĀ
# Function to remove sub-directories# from the given lists dirdef eraseSubdirectory(dir):Ā Ā Ā Ā Ā Ā Ā Ā Ā # Store final resultĀ Ā Ā Ā res = []Ā
Ā Ā Ā Ā # Sort the given directoriesĀ Ā Ā Ā dir.sort()Ā
Ā Ā Ā Ā # Insert 1st directoryĀ Ā Ā Ā res.append(dir[0])Ā
Ā Ā Ā Ā print("{", dir[0], end = ", ")Ā
Ā Ā Ā Ā # Iterating in directoryĀ Ā Ā Ā for i in range(1, len(dir)):Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā # Current directoryĀ Ā Ā Ā Ā Ā Ā Ā curr = dir[i]Ā
Ā Ā Ā Ā Ā Ā Ā Ā # Our previous valid directoryĀ Ā Ā Ā Ā Ā Ā Ā prev = res[len(res) - 1]Ā
Ā Ā Ā Ā Ā Ā Ā Ā # Find length of previous directoryĀ Ā Ā Ā Ā Ā Ā Ā l = len(prev)Ā
Ā Ā Ā Ā Ā Ā Ā Ā # If subdirectory is foundĀ Ā Ā Ā Ā Ā Ā Ā if (len(curr) > l andĀ Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā curr[l] == '/' andĀ Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā prev == curr[:l]):Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā continueĀ
Ā Ā Ā Ā Ā Ā Ā Ā # Else store it in resultĀ Ā Ā Ā Ā Ā Ā Ā # valid directoryĀ Ā Ā Ā Ā Ā Ā Ā res.append(curr)Ā Ā Ā Ā Ā Ā Ā Ā print(curr, end = ", ")Ā
Ā Ā Ā Ā print("}")Ā
# Driver Codeif __name__ == '__main__':Ā
Ā Ā Ā Ā # Given lists of directories dir[]Ā Ā Ā Ā dir = [ "/a", "/a/j", "/c/d/e", "/c/d", "/b" ]Ā
Ā Ā Ā Ā # Function CallĀ Ā Ā Ā eraseSubdirectory(dir)Ā
# This code is contributed by akhilsaini |
C#
// C# program for the above approachusing System;using System.Collections;Ā
class GFG{Ā
// Function to remove sub-directories// from the given lists dirstatic void eraseSubdirectory(ArrayList dir){Ā Ā Ā Ā Ā Ā Ā Ā Ā // Store final resultĀ Ā Ā Ā ArrayList res = new ArrayList();Ā
Ā Ā Ā Ā // Sort the given directoriesĀ Ā Ā Ā dir.Sort();Ā
Ā Ā Ā Ā // Insert 1st directoryĀ Ā Ā Ā res.Add(dir[0]);Ā
Ā Ā Ā Ā Console.Write("{" + dir[0] + ", ");Ā
Ā Ā Ā Ā // Iterating in directoryĀ Ā Ā Ā for(int i = 1; i < dir.Count; i++) Ā Ā Ā Ā {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // Current directoryĀ Ā Ā Ā Ā Ā Ā Ā string curr = (string)dir[i];Ā
Ā Ā Ā Ā Ā Ā Ā Ā // Our previous valid directoryĀ Ā Ā Ā Ā Ā Ā Ā string prev = (string)res[(res.Count - 1)];Ā
Ā Ā Ā Ā Ā Ā Ā Ā // Find length of previous directoryĀ Ā Ā Ā Ā Ā Ā Ā int l = prev.Length;Ā
Ā Ā Ā Ā Ā Ā Ā Ā // If subdirectory is foundĀ Ā Ā Ā Ā Ā Ā Ā if (curr.Length > l && curr[l] == '/' &&Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā prev.Equals(curr.Substring(0, l)))Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā continue;Ā
Ā Ā Ā Ā Ā Ā Ā Ā // Else store it in resultĀ Ā Ā Ā Ā Ā Ā Ā // valid directoryĀ Ā Ā Ā Ā Ā Ā Ā res.Add(curr);Ā
Ā Ā Ā Ā Ā Ā Ā Ā Console.Write(curr + ", ");Ā Ā Ā Ā }Ā Ā Ā Ā Console.Write("}\n");}Ā
// Driver Codepublic static void Main(){Ā Ā Ā Ā Ā Ā Ā Ā Ā // Given lists of directories dir[]Ā Ā Ā Ā ArrayList dir = new ArrayList(){ "/a", "/a/j", Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā "/c/d/e", Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā "/c/d", "/b" };Ā
Ā Ā Ā Ā // Function CallĀ Ā Ā Ā eraseSubdirectory(dir);}}Ā
// This code is contributed by akhilsaini |
Javascript
// Javascript program for the above approachĀ
// Function to remove sub-directories// from the given lists dirfunction eraseSubdirectory(dir) {Ā
Ā Ā Ā Ā // Store final resultĀ Ā Ā Ā let res = new Array();Ā
Ā Ā Ā Ā // Sort the given directoriesĀ Ā Ā Ā dir.sort();Ā
Ā Ā Ā Ā // Insert 1st directoryĀ Ā Ā Ā res.push(dir[0]);Ā
Ā Ā Ā Ā console.log("{" + dir[0] + ", ");Ā
Ā Ā Ā Ā // Iterating in directoryĀ Ā Ā Ā for (let i = 1; i < dir.length; i++) {Ā
Ā Ā Ā Ā Ā Ā Ā Ā // Current directoryĀ Ā Ā Ā Ā Ā Ā Ā let curr = dir[i];Ā
Ā Ā Ā Ā Ā Ā Ā Ā // Our previous valid directoryĀ Ā Ā Ā Ā Ā Ā Ā let prev = res[res.length - 1];Ā
Ā Ā Ā Ā Ā Ā Ā Ā // Find length of previous directoryĀ Ā Ā Ā Ā Ā Ā Ā let l = prev.length;Ā
Ā Ā Ā Ā Ā Ā Ā Ā // If subdirectory is foundĀ Ā Ā Ā Ā Ā Ā Ā if (curr.length > l &&Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā curr[l] == '/' && (prev == (curr.substring(0, l))))Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā continue;Ā
Ā Ā Ā Ā Ā Ā Ā Ā // Else store it in resultĀ Ā Ā Ā Ā Ā Ā Ā // valid directoryĀ Ā Ā Ā Ā Ā Ā Ā res.push(curr);Ā
Ā Ā Ā Ā Ā Ā Ā Ā console.log(curr + ", ");Ā Ā Ā Ā }Ā Ā Ā Ā console.log("}\n");}Ā
// Driver CodeĀ
// Given lists of directories dir[]let dir = ["/a", "/a/j", "/c/d/e", "/c/d", "/b"];Ā
// Function CalleraseSubdirectory(dir);Ā
Ā
// This code is contributed by Saurabh Jaiswal |
Output:Ā
{/a, /b, /c/d, }
Ā
Time Complexity: O(N*log N)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? Itās time for a change! Join our DSA course, where weāll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
