#388

Medium

auto_awesomeStack-based state management

LeetCode Problem Workspace

Longest Absolute File Path

Find the length of the longest absolute file path in a filesystem string using stack-based depth tracking efficiently.

Problem Statement

You are given a string representing a filesystem where directories and files are separated by newline characters '\n', and the depth of each entry is indicated by tab characters '\t'. A file contains a dot '.', whereas directories do not. Your task is to determine the length of the longest absolute path to a file in this filesystem.

For example, given a filesystem string, directories can contain subdirectories or files at arbitrary depths. You must compute the full path length by concatenating directory names with '/' separators, returning the maximum length among all files. The solution must handle deeply nested directories efficiently, using stack-based state management to track path lengths at each level.

Examples

Example 1

Input: See original problem statement.

Output: See original problem statement.

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

Example 2

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

Output: 20

We have only one file, and the absolute path is "dir/subdir2/file.ext" of length 20.

Example 3

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

Output: 32

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.

Constraints

1 <= input.length <= 104
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 Approach

Stack-Based Depth Tracking

Maintain a stack where each element represents the cumulative path length up to the current depth. Parse each line, determine its depth by counting '\t', and update the stack accordingly. Push new cumulative lengths for directories, and compute file lengths for files, updating the maximum path length.

Dynamic Path Length Calculation

When encountering a file, calculate the absolute path length by adding its name length to the cumulative length from the stack at the parent directory depth. Compare with the current maximum and update if larger. This ensures correct handling of multiple files at different depths.

Efficient Single-Pass Processing

Iterate over the input string line by line without building a full tree. Use the stack to backtrack when a line is at a shallower depth than the previous one. This avoids recursion and keeps time and space complexity linear relative to the input size.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) because each character of the input is processed once, with stack operations being O(1) per line. Space complexity is O(d) where d is the maximum directory depth, due to storing cumulative lengths in the stack.

What Interviewers Usually Probe

Are you keeping track of path lengths dynamically without building the full directory tree?
How do you handle tabs to correctly identify directory depth in your stack?
Can you update the maximum path efficiently as you parse each file?

Common Pitfalls or Variants

Common pitfalls

Miscounting depth by failing to handle multiple '\t' characters correctly.
Forgetting to include '/' separators in cumulative path length calculations.
Attempting recursion without stack optimization, causing O(n^2) behavior on deep inputs.

Follow-up variants

Return the actual longest absolute file path string instead of its length.
Count only files with a specific extension when computing the longest path.
Handle inputs where the filesystem string may contain empty lines or spaces at varying depths.

FAQ

What is the best way to parse tabs in Longest Absolute File Path?

Count consecutive '\t' characters at the start of each line to determine depth, then adjust the stack accordingly.

How do I handle multiple files at different depths efficiently?

Use a stack to maintain cumulative lengths at each depth and update the maximum path length when a file is encountered.

Can I solve this problem recursively instead of using a stack?

While recursion is possible, stack-based single-pass processing avoids repeated computations and is more efficient for deeply nested directories.

What should I do if a directory name contains dots?

Only consider entries as files if they contain a dot and are at the line's end; dots in directory names do not indicate files.

Why is this considered a Stack-based state management pattern?

Because you track cumulative path lengths by depth using a stack, pushing for deeper directories and popping when backtracking, which is the core pattern.

terminal

Solution

Solution 1

#### Python3

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

28

29

30

31

32

33

34

class Solution:
    def lengthLongestPath(self, input: str) -> int:
        i, n = 0, len(input)
        ans = 0
        stk = []
        while i < n:
            ident = 0
            while input[i] == '\t':
                ident += 1
                i += 1

            cur, isFile = 0, False
            while i < n and input[i] != '\n':
                cur += 1
                if input[i] == '.':
                    isFile = True
                i += 1
            i += 1

            # popd
            while len(stk) > 0 and len(stk) > ident:
                stk.pop()

            if len(stk) > 0:
                cur += stk[-1] + 1

            # pushd
            if not isFile:
                stk.append(cur)
                continue

            ans = max(ans, cur)

        return ans

Continue Practicing

#385 mini parser #399 evaluate division #402 remove k digits