1233. Remove Sub-Folders from the Filesystem

Time: O(n log n · m)

Space: O(n)

Intuition

A folder is a sub-folder of another if the other folder path + "/" is a prefix of it. Sort paths: a sub-folder always comes right after its parent.

Algorithm

1Sort paths lexicographically.
2Scan: for each path, check if it starts with prev_kept + "/". If yes, skip (sub-folder). Else keep and update prev_kept.

Common Pitfalls

•Must append "/" when checking prefix to avoid "/a/b" matching "/a/bc".

1233.cs

// Approach: Sort folders lexicographically; a folder is a sub-folder if it starts with the previous kept folder followed by '/'.
// Time: O(n log n · m) Space: O(n)

public class Solution
{
    public IList<string> RemoveSubfolders(string[] folder)
    {
        List<string> ans = new List<string>();
        string prev = "";

        Array.Sort(folder);

        foreach (var f in folder)
        {
            if (!string.IsNullOrEmpty(prev) && f.StartsWith(prev) && f[prev.Length] == '/')
                continue;
            ans.Add(f);
            prev = f;
        }

        return ans;
    }
}

Was this solution helpful?