Longest Absolute File Path Python Solution

Tested Python solution for LeetCode 388 with 18 pytest cases. Generate a practice environment with lcpy.

LeetCode 388, Medium. Topics: String, Stack, Depth-First Search. View on LeetCode.

Generate this problem as a practice environment: tested reference solution, 18 parametrized pytest cases, and a playground notebook:

lcpy gen -n 388   # by problem number
lcpy gen -s longest_absolute_file_path   # by problem name

​

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 (where each indented line is one level deeper):

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.

​

Examples

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.

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 and "dir/subdir2/subsubdir2/file2.ext" of length 32. We return 32 since it is the longest absolute path to a file.

Input: input = "a"
Output: 0

Explanation: We do not have any files, just a single directory named "a".

​

Constraints

• 1 <= input.length <= 10^4
• input may contain lowercase or uppercase English letters, a new line character '\n', a tab character '\t', a dot '.', a space ' ', and digits.
• All file and directory names have positive length.

​

Solution

Reference implementation from solution.py on GitHub, full suite in test_solution.py:

class Solution:
    # Time: O(n) single pass over the input
    # Space: O(d) stack of path lengths, d = max nesting depth
    def length_longest_path(self, input_str: str) -> int:
        best = 0
        # path_lens[i] = total length of the path ending at depth i (dirs only)
        path_lens: list[int] = []
        for line in input_str.split("\n"):
            depth = line.count("\t")
            name = line[depth:]
            del path_lens[depth:]
            parent = path_lens[-1] if path_lens else 0
            length = parent + (1 if path_lens else 0) + len(name)
            if "." in name:
                best = max(best, length)
            else:
                path_lens.append(length)
        return best

​

Complexity

Time	Space
O(n) single pass over the input	O(d) stack of path lengths, d = max nesting depth

​

Tags