Input:
input = "dir\n\tsubdir1\n\t\tfile1.ext\n\t\tsubsubdir1\n\tsubdir2\n\t\tsubsubdir2\n\t\t\tfile2.ext"
Output:
 32
Explanation: We have two files:
"dir/subdir1/file1.ext" of length 21
"dir/subdir2/subsubdir2/file2.ext" of length 32.
We return 32 since it is the longest absolute path to a file.

Example 3:

Input:
input = "a"
Output:
 0
Explanation: We do not have any files, just a single directory named "a".

Solution

Method 1 - Using Map

Algorithm

Lets take the example:

dir
 |
 ├── subdir1
 |   └── file1.ext
 └── subdir2
     └── file2.ext

I am denoting ⟶ for tab.

Split the string by newlines. lines = ["dir", "⟶subdir1", "⟶⟶file1.ext", "⟶subdir2", "⟶⟶file2.ext"]
Now for each line
1. Count number of tabs to determine the depth of the each line. In our example - "dir" (depth 0), "subdir1" (depth 1), "file1.ext" (depth 2), "subdir2" (depth 1), "file2.ext" (depth 2).`
Setup the map of depth to length of string so far.
Now, check if the line is a file or directory.
1. If it is a file, calculate the max length we had so far
2. If it is a directory, add the length to the map.

Lets try to dry run step 4. We see "dir", as it is not file. depth = 0. we add depth+1 to map: {1: 4}. "dir" is length 3, but we treat it as "dir/" hence length is 4.

"subdir1" ⇨ Again not a file. depth = 1, hence we add depth 2 to map: {1: 4, 2: 12}. We added depth as 12, which is len(dir/) + len(subdir1/) = 12.

"file1.ext" ⇨ It is a file. depth=2 hence we calculate length as 21, map stays the same. map.get(depth) + len(file1.ext) = 12 + 9 = 21.

Similarly we will do the same for remaining strings.

Code

[{"language":"Java","code":"class Solution {\n    public int lengthLongestPath(String input) {\n        String[] lines = input.split(\"\\n\");\n        int maxLength = 0;\n        HashMap<Integer, Integer> pathLengths = new HashMap<>(); // depth: length\n\n        for (String line : lines) {\n            String name = line.replaceAll(\"\\t\", \"\");\n            int depth = line.length() - name.length();\n            boolean isFile = name.contains(\".\");\n\n            if (isFile) {\n                maxLength = Math.max(maxLength, pathLengths.get(depth) + name.length());\n            } else {\n                pathLengths.put(depth + 1, pathLengths.getOrDefault(depth, 0) + name.length() + 1); // 1 for the '/'\n            }\n        }\n\n        return maxLength;\n    }\n}","lang":"java"}]

Complexity

⏰ Time complexity: O(n)
🧺 Space complexity: O(d) - Max depth of the files

Method 2 - Using Stack

Algorithm stays the same as previous method, but we will use stack to save the different depth or levels on the stack.

Code

[{"language":"Java","code":"class Solution {\n    public int lengthLongestPath(String input) {\n        String[] lines = input.split(\"\\n\");\n        int maxLength = 0, currLength = 0;\n\t\tStack<Integer> stack = new Stack<>();\n\t\tstack.push(0); \n\n        for (String line : lines) {\n            String name = line.replaceAll(\"\\t\", \"\");\n            int depth = line.length() - name.length();\n            \n            // if current directory/file depth is lower that the top directory/file on the stack, pop from stack \n            while(stack.size() > (depth + 1)) {\n\t            currLength -= stack.pop();\n            } \n            boolean isFile = name.contains(\".\");\n\t\t\t\n            if (isFile) {\n

Related Tags