Longest Absolute File Path: Stack-Based Depth Tracking

Longest Absolute File Path is LeetCode 388, rated Medium. You are given a string that represents a file system where "\n" separates entries and "\t" characters indicate nesting depth. Your job is to find the length of the longest absolute path to a file.

The trick is that the input looks like "dir\n\tsubdir1\n\t\tfile1.ext\n\t\tsubsubdir1\n\tsubdir2\n\t\tsubsubdir2\n\t\t\tfile2.ext". Each "\t" prefix tells you how deep a directory or file sits in the tree. You need to reconstruct the cumulative path lengths without actually building any strings.

The key insight

Count the "\t" characters at the start of each line to determine its depth. Then use a hash map (or array) to store the cumulative path length at each depth. When you encounter a line at depth d, its full path length is pathLengths[d - 1] + 1 + len(name), where the +1 accounts for the "/" separator. If the current entry is a file (it contains a "."), compare its cumulative length against your running maximum.

The hash map naturally handles backtracking. When you move from depth 3 back to depth 1, you simply overwrite pathLengths[1] with the new value. The old entries at deeper depths become irrelevant because any future child will compute from the updated parent.

The approach

Here is the full algorithm:

1. Split the input string by "\n" to get individual lines.
2. For each line, count the number of leading "\t" characters. That count is the depth.
3. The name is the rest of the line after stripping the tabs. Compute the cumulative path length: if depth is 0, the length is just len(name). Otherwise it is pathLengths[depth - 1] + 1 + len(name).
4. Store this cumulative length in pathLengths[depth].
5. If the name contains a ".", it is a file. Update the maximum with the cumulative length.
6. After processing all lines, return the maximum. If no file was found, return 0.

The code

def length_longest_path(input: str) -> int:
    path_lengths = {}
    max_len = 0

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

        if depth == 0:
            path_lengths[0] = len(name)
        else:
            path_lengths[depth] = path_lengths[depth - 1] + 1 + len(name)

        if "." in name:
            max_len = max(max_len, path_lengths[depth])

    return max_len

Let's walk through why this works so cleanly:

• Depth from tabs. line.count("\t") gives us the exact nesting level. Depth 0 is the root, depth 1 is one folder in, and so on.
• Cumulative lengths. We never build the actual path string. We only track how long the path would be at each depth. This avoids string concatenation overhead.
• Overwriting is safe. When two entries share the same depth, the second overwrites the first in the map. This is correct because we process lines top to bottom, and any entry at the same depth replaces its sibling. Children of the old entry were already processed.
• File detection. The problem states that file names always contain a "." and directory names never do. So "." in name is the check you need.

Complexity

Time: O(n). You split the string once (O(n)), then iterate through each line. For each line, counting tabs and stripping them are both proportional to the line length. Across all lines, the total work is proportional to the length of the input string.

Space: O(n). The split produces O(n) tokens. The hash map stores at most O(d) entries where d is the maximum depth, which is bounded by n. In the worst case (a single chain of nested directories), d could be proportional to n.

Building blocks

Depth tracking with hash map

The core pattern here is using a dictionary keyed by depth to track cumulative state. You have seen this in problems where nesting or levels matter. Instead of maintaining an explicit stack and pushing/popping, you let the hash map handle it implicitly. Writing pathLengths[depth] = value is equivalent to "set the stack to this state at this depth." It is simpler than maintaining a real stack because you do not need to pop entries when the depth decreases.

This same pattern appears in problems like level-order traversals where you accumulate results by depth, or nested structures where each level contributes to a running calculation.

Edge cases

• No file in the input. If the input is "dir\n\tsubdir" with no file at all, no entry ever contains a dot, so max_len stays 0. Return 0.
• File at root level. If the input is just "file.txt", the depth is 0 and the path length is 8. The answer is 8. There is no leading slash in the return value.
• Multiple files at the same depth. Each file overwrites pathLengths[depth], but that is fine because you compare against max_len before moving on. Both files get checked.

From understanding to recall

This problem has a clean, compact solution. The entire thing fits in about 10 lines. But under pressure, the details trip people up. Do you count tabs or strip them? Do you add +1 for the separator at depth 0 or only at deeper levels? When do you check for a file versus a directory?

These are recall gaps, not understanding gaps. You get the idea right now, but reproducing the code from scratch three weeks from now requires practice. Spaced repetition closes that gap. You write the solution from memory at increasing intervals, and each repetition reinforces the depth counting, the cumulative length formula, and the file detection check. After a few rounds, the whole thing is automatic.

Related posts

• Simplify Path - Another path-processing problem where you parse structured tokens and track directory state
• Basic Calculator - Uses a stack to track nested state at different levels of depth, similar to the depth tracking here
• Min Stack - Stack-based state tracking where you maintain auxiliary information alongside the main data