Intuition

The problem requires removing subfolders from a list of folder paths. The simplest way to identify subfolders is to check if one path starts with another parent path. By sorting the folders lexicographically, subfolders will always appear immediately after their corresponding parent folders, which makes it easy to filter them out with a single pass through the list.

Approach

1. Sort the Folders: First, we sort the list of folders lexicographically. This ensures that any subfolder will appear directly after its parent folder in the list.
2. Filter Subfolders: We initialize an empty result array. Then, we iterate over the sorted list and add each folder to the result if it does not start with the most recent folder in the result (plus a trailing /). This way, we can filter out any subfolder by simple string comparison.

Complexity

• Time complexity: Sorting the folders takes O(nlog⁡n)O(n \log n)O(nlogn), where nnn is the number of folders. The subsequent pass through the list to filter out subfolders is O(n)O(n)O(n). Therefore, the overall time complexity is O(nlog⁡n)O(n \log n)O(nlogn).
• Space complexity: O(n)O(n)O(n), as we store the filtered folders in a separate result array.

Problem

Given a list of folders folder, return the folders after removing all sub-folders in those folders. You may return the answer in any order.

If a folder[i] is located within another folder[j], it is called a sub-folder of it. A sub-folder of folder[j] must start with folder[j], followed by a "/". For example, "/a/b" is a sub-folder of "/a", but "/b" is not a sub-folder of "/a/b/c".

The format of a path is one or more concatenated strings of the form: '/' followed by one or more lowercase English letters.

• For example, "/leetcode" and "/leetcode/problems" are valid paths while an empty string and "/" are not.

Example 1:

Input: folder = ["/a","/a/b","/c/d","/c/d/e","/c/f"]
Output: ["/a","/c/d","/c/f"]
Explanation: Folders "/a/b" is a subfolder of "/a" and "/c/d/e" is inside of folder "/c/d" in our filesystem.

Example 2:

Input: folder = ["/a","/a/b/c","/a/b/d"]
Output: ["/a"]
Explanation: Folders "/a/b/c" and "/a/b/d" will be removed because they are subfolders of "/a".

Example 3:

Input: folder = ["/a/b/c","/a/b/ca","/a/b/d"]
Output: ["/a/b/c","/a/b/ca","/a/b/d"]

Constraints:

• 1 <= folder.length <= 4 * 104
• 2 <= folder[i].length <= 100
• folder[i] contains only lowercase letters and '/'.
• folder[i] always starts with the character '/'.
• Each folder name is unique.

LeetCode

Code

class Solution {

    /**
     * @param String[] $folder
     * @return String[]
     */
    function removeSubfolders($folder) {
        sort($folder);
        $result = [];

    foreach ($folder as $f) {
        if (empty($result) || strpos($f, end($result) . '/') !== 0) {
            $result[] = $f;
        }
    }
    
    return $result;
    }
}

Github

Explanation

1. Sorting: Sorting the folders lexicographically places each parent folder directly before its subfolders. For instance, "/a" will appear before "/a/b", "/c/d" will appear before "/c/d/e", and so on.
2. Checking Subfolders: After sorting, we use strpos() to check if each folder starts with the last folder added to result plus a /. If it doesn’t, it’s a new parent folder and is added to result; otherwise, it’s considered a subfolder and skipped.
3. Output: The result array will contain only the root folders after removing subfolders.