Problem

Suppose we have a file system that stores both files and directories. An example of one system is represented in the following picture:

Here, we have dir as the only directory in the root. dir contains two subdirectories, subdir1 and subdir2. subdir1 contains a file file1.ext and subdirectory subsubdir1. subdir2 contains a subdirectory subsubdir2, which contains a file file2.ext.

In text form, it looks like this (with ⟶ representing the tab character):

1
2
3
4
5
6
7

dir
⟶ subdir1
⟶ ⟶ file1.ext
⟶ ⟶ subsubdir1
⟶ subdir2
⟶ ⟶ subsubdir2
⟶ ⟶ ⟶ file2.ext

If we were to write this representation in code, it will look like this: "dir\n\tsubdir1\n\t\tfile1.ext\n\t\tsubsubdir1\n\tsubdir2\n\t\tsubsubdir2\n\t\t\tfile2.ext". Note that the '\n' and '\t' are the new-line and tab characters.

Every file and directory has a unique absolute path in the file system, which is the order of directories that must be opened to reach the file/directory itself, all concatenated by '/'s. Using the above example, the absolute path to file2.ext is "dir/subdir2/subsubdir2/file2.ext". Each directory name consists of letters, digits, and/or spaces. Each file name is of the form name.extension, where name and extension consist of letters, digits, and/or spaces.

Given a string input representing the file system in the explained format, return the length of the longest absolute path to a file in the abstracted file system. If there is no file in the system, return 0.

Note that the testcases are generated such that the file system is valid and no file or directory name has length 0.

Use below to remove images:

1
2
3
4

user
	pictures
	documents
		notes.txt

|The directory user contains an empty sub-directory pictures and a sub-directory documents containing a file notes.txt.

The string "user\n\tpictures\n\t\tphoto.png\n\t\tcamera\n\tdocuments\n\t\tlectures\n\t\t\tnotes.txt".

Examples

Example 1:

1
2
3
4
5

dir
 |
 |-- subdir1
 |-- subdir2
     |-- file.ext

1
2
3
4
5

Input:
input = "dir\n\tsubdir1\n\tsubdir2\n\t\tfile.ext"
Output:
 20
Explanation: We have only one file, and the absolute path is "dir/subdir2/file.ext" of length 20.

Example 2:

1
2
3
4
5
6
7
8

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

1
2
3
4
5
6
7
8

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:

1
2
3
4
5

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:

1
2
3
4
5
6

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

I am denoting ⟶ for tab.

  1. Split the string by newlines. lines =  ["dir", "⟶subdir1", "⟶⟶file1.ext", "⟶subdir2", "⟶⟶file2.ext"]
  2. 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).`
  3. Setup the map of depth to length of string so far.
  4. 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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
    public int lengthLongestPath(String input) {
        String[] lines = input.split("\n");
        int maxLength = 0;
        HashMap<Integer, Integer> pathLengths = new HashMap<>(); // depth: length

        for (String line : lines) {
            String name = line.replaceAll("\t", "");
            int depth = line.length() - name.length();
            boolean isFile = name.contains(".");

            if (isFile) {
                maxLength = Math.max(maxLength, pathLengths.get(depth) + name.length());
            } else {
                pathLengths.put(depth + 1, pathLengths.getOrDefault(depth, 0) + name.length() + 1); // 1 for the '/'
            }
        }

        return maxLength;
    }
}

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

class Solution {
    public int lengthLongestPath(String input) {
        String[] lines = input.split("\n");
        int maxLength = 0, currLength = 0;
		Stack<Integer> stack = new Stack<>();
		stack.push(0); 

        for (String line : lines) {
            String name = line.replaceAll("\t", "");
            int depth = line.length() - name.length();
            
            // if current directory/file depth is lower that the top directory/file on the stack, pop from stack 
            while(stack.size() > (depth + 1)) {
	            currLength -= stack.pop();
            } 
            boolean isFile = name.contains(".");
			
            if (isFile) {
                maxLength = Math.max(maxLength, stack.peek() + name.length());
            } else {
                stack.push(stack.peek() + (name.length() + 1)); // +1 for "/"
            }
        }

        return maxLength;
    }
}

Complexity

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