LeetCode 388: Longest Absolute File Path

Problem Restatement

We are given a string input that represents a file system.

Each file or directory appears on its own line.

A newline character means a new entry:

"\n"

A tab character at the start of a line tells us the depth:

"\t"

A file is identified by having a dot . in its name.

We need to return the length of the longest absolute path to any file. If there is no file, return 0.

For example, this path:

dir/subdir2/subsubdir2/file2.ext

has length 32.

Input and Output

Example function shape:

def lengthLongestPath(input: str) -> int:
    ...

Examples

Example 1:

input = "dir\n\tsubdir1\n\tsubdir2\n\t\tfile.ext"

This represents:

dir
    subdir1
    subdir2
        file.ext

The file path is:

dir/subdir2/file.ext

Its length is:

len("dir/subdir2/file.ext") == 20

So the answer is:

20

Example 2:

input = "dir\n\tsubdir1\n\t\tfile1.ext\n\t\tsubsubdir1\n\tsubdir2\n\t\tsubsubdir2\n\t\t\tfile2.ext"

The files are:

dir/subdir1/file1.ext
dir/subdir2/subsubdir2/file2.ext

Their lengths are:

len("dir/subdir1/file1.ext") == 21
len("dir/subdir2/subsubdir2/file2.ext") == 32

So the answer is:

32

Example 3:

input = "a"

There is only a directory and no file.

So the answer is:

0

First Thought: Build the Whole Tree

One direct approach is to parse the string into an actual tree.

Each directory becomes a tree node.

Each file becomes a leaf.

Then we can traverse the tree and compute every file path length.

This works, but it is more structure than we need.

We do not need the tree itself. We only need the current path length at each depth.

Key Insight

When reading a line, its number of leading tabs gives its depth.

For example:

dir                  depth 0
    subdir2          depth 1
        file.ext     depth 2

If we know the full path length up to depth 1, then we can compute the file path at depth 2.

For:

dir/subdir2/file.ext

we need:

len("dir/subdir2/") + len("file.ext")

So we keep a table:

path_len[depth]

where path_len[d] means the total length of the path prefix up to depth d, including the trailing slash.

For example:

path_len[0] = len("dir/")
path_len[1] = len("dir/subdir2/")

Then when we see a file at depth 2, its full length is:

path_len[1] + len("file.ext")

Algorithm

Split the input into lines:

lines = input.split("\n")

Create a map for prefix lengths:

path_len = {0: 0}

Here, path_len[0] = 0 means there is no prefix before a root-level entry.

For each line:

1. Count the number of leading tabs. This is depth.
2. Remove those tabs to get the name.
3. If the name contains ., it is a file.
   • Its full path length is path_len[depth] + len(name).
   • Update the answer.
4. Otherwise, it is a directory.
   • Store the prefix length for its children:

   path_len[depth + 1] = path_len[depth] + len(name) + 1
   The + 1 is for the slash /.

Correctness

The value path_len[d] stores the length of the absolute path prefix before an entry at depth d.

For depth 0, this prefix is empty, so path_len[0] = 0.

When the parser reads a directory at depth d, every child of that directory appears at depth d + 1. The child prefix consists of the parent prefix, the directory name, and one slash. Therefore:

path_len[d + 1] = path_len[d] + len(name) + 1

is correct.

When the parser reads a file at depth d, its absolute path consists of the prefix before depth d plus the file name. Therefore:

path_len[d] + len(name)

is exactly the file path length.

The algorithm evaluates every file line and takes the maximum of these exact lengths. If no file appears, the maximum remains 0.

Therefore the returned value is the length of the longest absolute path to a file.

Complexity

Let n = len(input).

d is the maximum directory nesting depth.

Implementation

class Solution:
    def lengthLongestPath(self, input: str) -> int:
        path_len = {0: 0}
        best = 0

        for line in input.split("\n"):
            depth = line.count("\t")
            name = line.lstrip("\t")

            if "." in name:
                best = max(best, path_len[depth] + len(name))
            else:
                path_len[depth + 1] = path_len[depth] + len(name) + 1

        return best

Code Explanation

We store prefix lengths by depth:

path_len = {0: 0}

The root level has no parent prefix.

The answer starts at 0:

best = 0

We process each file-system entry line by line:

for line in input.split("\n"):

The depth is the number of leading tabs:

depth = line.count("\t")

In this problem, tabs appear only as indentation at the start of a line, so this gives the depth.

Remove the tabs to get the actual file or directory name:

name = line.lstrip("\t")

If the name contains a dot, it is a file:

if "." in name:

Then compute the absolute path length:

path_len[depth] + len(name)

If the name is a directory, compute the prefix length for its children:

path_len[depth + 1] = path_len[depth] + len(name) + 1

The + 1 accounts for the slash between path components.

Testing

def test_solution():
    s = Solution()

    assert s.lengthLongestPath(
        "dir\n\tsubdir1\n\tsubdir2\n\t\tfile.ext"
    ) == 20

    assert s.lengthLongestPath(
        "dir\n\tsubdir1\n\t\tfile1.ext\n\t\tsubsubdir1\n"
        "\tsubdir2\n\t\tsubsubdir2\n\t\t\tfile2.ext"
    ) == 32

    assert s.lengthLongestPath("a") == 0

    assert s.lengthLongestPath("file.txt") == 8

    assert s.lengthLongestPath(
        "a\n\tb\n\t\tc.txt\n\td.txt"
    ) == 9

    assert s.lengthLongestPath(
        "dir\n\tfile.txt\n\tlongdirname\n\t\tlongfile.txt"
    ) == len("dir/longdirname/longfile.txt")

    print("all tests passed")

test_solution()

Test meaning: