Watch 10 video solutions for Longest Absolute File Path, a medium level problem involving String, Stack, Depth-First Search. This walkthrough by NeetCode has 73,047 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 (with ⟶ representing the tab character):
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.
Example 1:
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.
Example 2:
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 "dir/subdir2/subsubdir2/file2.ext" of length 32. We return 32 since it is the longest absolute path to a file.
Example 3:
Input: input = "a" Output: 0 Explanation: We do not have any files, just a single directory named "a".
Constraints:
1 <= input.length <= 104input may contain lowercase or uppercase English letters, a new line character '\n', a tab character '\t', a dot '.', a space ' ', and digits.Problem Overview: The input string encodes a file system where \n separates entries and \t indicates directory depth. Directories and files appear in a tree-like structure, and files contain a dot (.). Your task is to compute the length of the longest absolute path to any file.
The challenge is reconstructing path lengths without explicitly building the entire directory tree. Each line tells you two things: its depth in the hierarchy and the name length. Efficient solutions track cumulative path lengths for each depth while scanning the string once.
Approach 1: Depth-based Path Tracking (O(n) time, O(d) space)
This method keeps a mapping or array where depthLengths[d] stores the total path length up to that depth. While iterating through each line of the input, count the number of \t characters to determine its depth, then compute the current path length using the parent directory length at depth - 1. If the entry is a directory, update the stored length for that depth; if it is a file (contains .), update the global maximum path length.
The key insight is that you only need cumulative lengths, not the actual path strings. Each directory contributes name_length + 1 to account for the slash separator. This avoids constructing paths and keeps the algorithm linear. Time complexity is O(n) because every character is processed once, and space complexity is O(d), where d is the maximum directory depth.
Approach 2: Stack-based Path Calculation (O(n) time, O(d) space)
This approach uses a stack to simulate traversal of the directory tree. Each stack element stores the cumulative length of the path at that depth. As you process each entry, compute its depth from the number of \t characters. If the current depth is smaller than the stack size, repeatedly pop until the stack matches the correct parent level.
Once aligned, calculate the new path length by adding the current name length to the parent path length stored on the stack. If the entry is a directory, push the new cumulative length onto the stack. If it is a file, update the maximum length encountered. This method mirrors how a stack tracks nested structures and is intuitive for problems involving hierarchical parsing.
Both solutions rely heavily on string parsing and depth tracking, making them strong exercises for string manipulation and hierarchical traversal patterns similar to depth-first search. The filesystem structure behaves like a tree, even though it is encoded as a flat string.
Recommended for interviews: The depth-based path tracking solution is typically preferred. It uses a simple array or map and avoids stack operations while maintaining the same O(n) time complexity. Interviewers often expect candidates to recognize that the problem only requires cumulative lengths per depth rather than reconstructing full paths. Demonstrating the stack version first shows understanding of the hierarchy, while the optimized depth-tracking approach demonstrates strong problem-solving instincts.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Depth-based Path Tracking | O(n) | O(d) | Preferred solution for interviews; simple logic using cumulative lengths per depth |
| Stack-based Path Calculation | O(n) | O(d) | Useful when modeling the directory hierarchy explicitly with a stack |