LeetCode 388 - Longest Absolute File Path

LeetCode Problem 388

Difficulty: 🟡 Medium
Topics: String, Stack, Depth-First Search

Solution

Problem Understanding

The problem gives us a string representation of a file system hierarchy. Every line represents either a directory or a file. The hierarchy is encoded using newline characters (\n) to separate entries and tab characters (\t) to indicate nesting depth.

A line with no leading tabs exists at depth 0, meaning it is directly under the root. A line with one leading tab exists inside the previous depth 0 directory, a line with two tabs exists one level deeper, and so on.

A file is identified by the presence of a dot (.) in its name. Directories do not contain dots. The task is to compute the length of the longest absolute path that leads to a file.

For example, consider this structure:

dir
    subdir2
        file.ext

The corresponding absolute path is:

dir/subdir2/file.ext

The answer is the number of characters in that path, including the / separators.

The constraints are important because the input length can be up to 10^4, which means we should avoid repeatedly rebuilding long strings or performing expensive recursive traversals. A linear-time solution is expected.

There are several edge cases that can easily cause bugs if handled incorrectly.

A filesystem may contain no files at all. In that case, the correct answer is 0.

A file may exist directly under the root directory without nested folders.

Multiple directories may exist at the same depth, so we need to correctly discard previous branches when moving back up the hierarchy.

Directory names and file names may contain spaces and digits, which means we cannot rely on simplistic parsing assumptions other than tabs and newlines.

The input is guaranteed to represent a valid filesystem, and every file or directory name has positive length.

Approaches

Brute Force Approach

A straightforward approach is to explicitly reconstruct the full path for every file.

We can process each line one by one, determine its depth from the number of leading tabs, and maintain the current directory hierarchy in a stack. Whenever we encounter a file, we join all directory names and the file name together using / separators and compute the resulting string length.

This approach is correct because the stack always represents the current path from the root to the current entry. Every time we see a file, constructing the path from the stack gives the exact absolute path.

However, this method is inefficient because joining strings repeatedly can become expensive. If there are many deeply nested files, we may repeatedly rebuild nearly identical paths. In the worst case, each file path construction costs O(n), leading to quadratic complexity overall.

Optimal Approach

The key insight is that we do not actually need to construct the full path strings. We only need their lengths.

Instead of storing full path components, we can store the cumulative path length at each depth level.

For every line:

• Determine its depth
• Remove the leading tabs
• Compute the current path length based on the parent directory length
• If the entry is a file, update the maximum answer
• If the entry is a directory, store its cumulative length for future children

This works because every absolute path is simply:

parent_path + "/" + current_name

So if we already know the total length up to the parent directory, we can compute the new length in constant time.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(n)	Repeatedly rebuilds full path strings
Optimal	O(n)	O(n)	Stores cumulative path lengths by depth

Algorithm Walkthrough

1. Split the input string by newline characters.

Each resulting line represents either a file or a directory. 2. Maintain a mapping from depth to cumulative path length.

For example:

depth_lengths[2] = 15

means that the total length of the absolute path up to depth 2 is 15. 3. Initialize the root depth length.

We set:

depth_lengths[0] = 0

This represents an empty base path before processing any entries. 4. Process each line individually.

For every line:

• Count the number of leading \t characters
• This count represents the depth
• Remove the tabs to obtain the actual name

5. Compute the current path length.

Suppose the current entry is at depth d.

Its parent directory is at depth d - 1.

The total path length becomes:

parent_length + len(name)

If the depth is greater than 0, we also add 1 for the / separator. 6. Check whether the entry is a file.

If the name contains a dot (.), it is a file.

Update the maximum path length if this path is longer than the previous best. 7. Otherwise, store the directory length.

If the entry is a directory, future children will use this path length as their parent length. 8. Continue until all lines are processed. 9. Return the maximum file path length found.

Why it works

The algorithm maintains the invariant that depth_lengths[d] always stores the total absolute path length up to depth d.

When processing a child node, its full path length depends only on its parent path length and its own name length. Since the parent length is already known, each new path length can be computed in constant time.

Because every line is processed exactly once, and because the cumulative lengths always reflect the correct filesystem hierarchy, the algorithm correctly computes the longest absolute file path.

Python Solution

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

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

            current_length = depth_lengths[depth] + len(name)

            if "." in name:
                max_length = max(max_length, current_length)
            else:
                depth_lengths[depth + 1] = current_length + 1

        return max_length

The implementation begins by creating a dictionary called depth_lengths. This dictionary maps each depth level to the cumulative path length up to that depth.

The value for depth 0 is initialized to 0, which represents the empty starting point before any directories are processed.

The input string is split using newline characters so that each filesystem entry can be processed independently.

For every line, the number of leading tabs determines the depth. The actual file or directory name is obtained by removing those tabs.

The variable current_length represents the total path length for the current entry. It is computed using the stored parent length plus the length of the current name.

If the current entry contains a dot, it is treated as a file. The algorithm updates max_length if this file path is the longest encountered so far.

Otherwise, the entry is a directory. In that case, the algorithm stores the cumulative length for the next depth level. The extra 1 accounts for the / separator that future children will require.

Finally, the algorithm returns the maximum file path length found during traversal.

Go Solution

package main

import (
	"strings"
)

func lengthLongestPath(input string) int {
	depthLengths := map[int]int{
		0: 0,
	}

	maxLength := 0

	lines := strings.Split(input, "\n")

	for _, line := range lines {
		depth := strings.Count(line, "\t")
		name := strings.TrimLeft(line, "\t")

		currentLength := depthLengths[depth] + len(name)

		if strings.Contains(name, ".") {
			if currentLength > maxLength {
				maxLength = currentLength
			}
		} else {
			depthLengths[depth+1] = currentLength + 1
		}
	}

	return maxLength
}

The Go implementation follows the same logic as the Python version. A map stores cumulative path lengths indexed by depth.

The primary language-specific differences are related to string handling. Go uses functions from the strings package to count tabs, remove leading tabs, and detect file names.

Go strings are immutable, just like Python strings, so operations such as trimming and splitting produce new values.

No special integer overflow handling is needed because the maximum input size is small relative to Go's integer capacity.

Worked Examples

Example 1

Input:

dir
    subdir1
    subdir2
        file.ext

Actual encoded input:

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

Step-by-step Trace

Line	Depth	Name	Current Length	File?	depth_lengths	max_length
dir	0	dir	3	No	{0:0, 1:4}	0
\tsubdir1	1	subdir1	11	No	{0:0, 1:4, 2:12}	0
\tsubdir2	1	subdir2	11	No	{0:0, 1:4, 2:12}	0
\t\tfile.ext	2	file.ext	20	Yes	unchanged	20

Final answer:

20

The longest path is:

dir/subdir2/file.ext

Example 2

Input:

dir
    subdir1
        file1.ext
        subsubdir1
    subdir2
        subsubdir2
            file2.ext

Step-by-step Trace

Line	Depth	Name	Current Length	File?	max_length
dir	0	dir	3	No	0
\tsubdir1	1	subdir1	11	No	0
\t\tfile1.ext	2	file1.ext	21	Yes	21
\t\tsubsubdir1	2	subsubdir1	22	No	21
\tsubdir2	1	subdir2	11	No	21
\t\tsubsubdir2	2	subsubdir2	22	No	21
\t\t\tfile2.ext	3	file2.ext	32	Yes	32

Final answer:

32

The longest path is:

dir/subdir2/subsubdir2/file2.ext

Example 3

Input:

"a"

Step-by-step Trace

Line	Depth	Name	Current Length	File?	max_length
a	0	a	1	No	0

No files are present, so the answer remains:

0

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each character is processed a constant number of times
Space	O(n)	The depth map may store information for many nested directories

The algorithm processes every line exactly once and performs only constant-time work per character. No repeated path reconstruction occurs, which avoids quadratic behavior.

The auxiliary space comes from the depth mapping. In the worst case, the filesystem may contain deeply nested directories, requiring storage proportional to the input size.

Test Cases

solution = Solution()

# Provided examples
assert solution.lengthLongestPath(
    "dir\n\tsubdir1\n\tsubdir2\n\t\tfile.ext"
) == 20  # basic nested file

assert solution.lengthLongestPath(
    "dir\n\tsubdir1\n\t\tfile1.ext\n\t\tsubsubdir1\n"
    "\tsubdir2\n\t\tsubsubdir2\n\t\t\tfile2.ext"
) == 32  # deeper nested longest file

assert solution.lengthLongestPath("a") == 0  # no files present

# Single file at root
assert solution.lengthLongestPath("file.txt") == 8  # root-level file

# Multiple root files
assert solution.lengthLongestPath(
    "a.txt\nlongfilename.ext"
) == 16  # choose longest root file

# Deep nesting
assert solution.lengthLongestPath(
    "dir\n\tsub1\n\t\tsub2\n\t\t\tsub3\n\t\t\t\tfile.ext"
) == 27  # deeply nested structure

# Directory names with spaces
assert solution.lengthLongestPath(
    "my dir\n\tsub dir\n\t\tfile name.ext"
) == 32  # spaces inside names

# Multiple sibling directories
assert solution.lengthLongestPath(
    "dir\n\ta\n\t\tfile1.txt\n\tb\n\t\tfile2.txt"
) == 15  # switching between sibling branches

# File directly under root directory
assert solution.lengthLongestPath(
    "dir\n\tfile.txt"
) == 12  # simple parent-child case

# Longest file not deepest
assert solution.lengthLongestPath(
    "dir\n\tshort\n\t\tf.ext\n\tverylongdirectory\n\t\ta.ext"
) == 29  # longest path determined by directory length

Test Summary

Test	Why
Basic nested file	Verifies standard hierarchy parsing
Deep nested example	Validates multi-level directory traversal
No files present	Ensures result is 0 when no files exist
Single root file	Confirms root-level file handling
Multiple root files	Ensures longest file is selected
Deep nesting	Tests many depth levels
Names with spaces	Confirms spaces are parsed correctly
Multiple sibling directories	Ensures depth transitions work properly
File directly under root	Verifies simple parent-child paths
Longest file not deepest	Confirms length calculation is correct

Edge Cases

No Files in the Filesystem

A filesystem may contain only directories and no files at all. This is important because a naive implementation might incorrectly return the longest directory path instead of 0.

For example:

dir
    subdir

Since no entry contains a dot, the correct answer is 0.

The implementation handles this correctly because max_length is updated only when a file is encountered.

Files at the Root Level

A file may appear directly at depth 0 without any parent directory.

For example:

file.txt

This case is easy to mishandle if the algorithm assumes every file has a parent directory.

The implementation avoids this issue because depth_lengths[0] is initialized to 0, allowing root-level file lengths to be computed naturally.

Moving Back Up the Directory Hierarchy

A common bug occurs when processing sibling directories after returning from deeper nesting levels.

For example:

dir
    a
        file1.txt
    b
        file2.txt

When processing b, the algorithm must ignore the previously nested path under a.

The implementation handles this correctly because path lengths are indexed by depth. When a new directory appears at the same depth, it overwrites the previous entry for that depth, ensuring future children use the correct parent path.