Skip to main content
Talentd

Longest Absolute File Path - Solution & Explanation

MediumStringStackDepth-First Search19 min readAsked at: Amazon, Microsoft, Meta +1
Practice this problem

Problem Statement

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 <= 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.

Approach Overview

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 1: Depth-based Path Tracking

This approach involves splitting the input based on newline characters to get directory and file names. By counting the number of tabs (\t), we can determine the depth of each line. Using a dictionary or an array to maintain the length of directories at different depths, we can construct the paths efficiently. When a file is encountered, we compute its path length and update the maximum length encountered so far. This approach leverages the property that each increase in depth indicates a sub-directory or file within a parent.

We maintain a dictionary pathlen to store the cumulative length of directory strings at each depth level. For every line, we compute the depth by counting the leading tab characters. If the line represents a file (determined by checking for a dot), we calculate the total path length, compare it, and update the maxlen if it's greater. Otherwise, we add the directory length to the path length stored in pathlen at the next depth level.

Code

PythonC++JavaCC#JavaScript

Python

C++

Java

C

C#

JavaScript

Complexity

Time Complexity: O(n), where n is the length of the input string as each character is processed once.
Space Complexity: O(n) in the worst case when the directory structure is deeply nested such that each level depth count is stored.

Try this approach in the editor →

Approach 2: Stack-based Path Calculation

This alternative approach involves using a stack data structure to handle the directory structure as we parse each name from the input. Instead of directly managing directory lengths, we push the length of each valid path segment onto the stack and pop when necessary. This stack helps in backtracking to the previous state when handling files or subdirectories at different levels. Whenever a file is detected, the sum of current stack elements plus the file length gives the full path length. The procedure keeps updating the maximum observed path length whenever a file node is processed.

In this approach, we maintain a stack that holds path lengths for each depth. For each line from the input, which signifies either a directory or a file with a specified depth, we adjust the stack size to represent the correct directory level. If a file is encountered (a dot in the name), the total length is computed as the sum of the stack and compared to update the maximum length observed.

Code

PythonC++JavaCC#JavaScript

Python

C++

Java

C

C#

JavaScript

Complexity

Time Complexity: O(n), where n refers to the length of the input string.
Space Complexity: O(d), with d being the maximum depth of directory captured by the stack.

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Depth-based Path Tracking

Time Complexity: O(n), where n is the length of the input string as each character is processed once.
Space Complexity: O(n) in the worst case when the directory structure is deeply nested such that each level depth count is stored.

Stack-based Path Calculation

Time Complexity: O(n), where n refers to the length of the input string.
Space Complexity: O(d), with d being the maximum depth of directory captured by the stack.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Depth-based Path TrackingO(n)O(d)Preferred solution for interviews; simple logic using cumulative lengths per depth
Stack-based Path CalculationO(n)O(d)Useful when modeling the directory hierarchy explicitly with a stack

Video Solution

Longest Absolute File Path | Top Google Coding Interview Question • Coding Courses • 4,254 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Longest Absolute File Path easy or hard?
Longest Absolute File Path is categorized as a medium difficulty problem. The main challenge is interpreting the encoded filesystem structure and efficiently maintaining path lengths without building the full directory tree.
Longest Absolute File Path Python/Java solution
Python and Java implementations usually parse the string using split("\n") to process each filesystem entry. Depth is calculated by counting leading tabs, and cumulative path lengths are tracked using either a stack or a depth-length array. Both implementations achieve O(n) time complexity.
How to solve Longest Absolute File Path in O(n)?
Parse the string line by line using the newline delimiter. Count the number of leading tab characters to determine the depth, then compute the cumulative path length using the parent directory length. When a filename containing a dot is found, update the maximum path length. Using either a depth-length array or a stack ensures linear time complexity.
What is the best approach for Longest Absolute File Path?
The depth-based path tracking approach is generally the best. It keeps cumulative path lengths for each directory depth and updates the maximum when a file is encountered. The algorithm scans the input once, achieving O(n) time complexity and O(d) space where d is the maximum depth.
Is Longest Absolute File Path asked at Google/Amazon/Meta?
Longest Absolute File Path is a common medium-level interview problem focused on string parsing and hierarchical structures. Variants of filesystem or tree parsing problems have appeared in interviews at companies like Amazon and Google, making it useful practice for real interview scenarios.
What data structure is used in Longest Absolute File Path?
Typical solutions use either a stack or an array/map indexed by depth. The stack simulates traversal through nested directories, while the depth-indexed array stores cumulative path lengths for each level. Both approaches rely heavily on string processing and hierarchical tracking.
What is the time complexity of Longest Absolute File Path?
The optimal solutions run in O(n) time, where n is the length of the input string. Each line and character is processed once while determining depth and updating cumulative path lengths. Space complexity is O(d), where d represents the maximum directory nesting depth.

Ready to solve this problem?

Practice Longest Absolute File Path with our built-in code editor and test cases.

Practice on FleetCode
Previous

Longest Substring Without Repeating Characters

Next

Longest Palindromic Substring