388. Longest Absolute File Path
Problem Description
Suppose there is a file system that organizes files and directories. In this file system, files and directories are represented in a string with a specific format, where:
\n
marks the end of a directory or file name (effectively, this is a newline character).\t
denotes a level of indentation, representing that a file or directory is nested within a directory (this is a tab character).
The goal is to compute the length of the longest absolute path to a file within this system. An absolute path is the path that starts from the root and includes all directories leading up to the file, separated by slashes ('/'
). If there are no files in the system, the function should return 0
.
To illustrate, a file system could be represented like this as a string:
"dir\n\tsubdir1\n\t\tfile1.ext\n\t\tsubsubdir1\n\tsubdir2\n\t\tsubsubdir2\n\t\t\tfile2.ext"
Here, the longest absolute path is to file2.ext
, and the absolute path for this file is "dir/subdir2/subsubdir2/file2.ext"
.
We need to create an algorithm that can interpret this string representation and determine the longest absolute path to any file in it.
Flowchart Walkthrough
Let's analyze the problem using the Flowchart. Here's the step-by-step walkthrough for LeetCode 388. Longest Absolute File Path:
Is it a graph?
- Yes: Although not a typical graph problem, the file structure can be imagined as a tree, where each directory is a node, and subdirectories/files are child nodes.
Is it a tree?
- Yes: The file system is usually represented as a tree where each folder is a parent node and files/subfolders are child nodes.
Is the problem related to directed acyclic graphs (DAGs)?
- Not applicable here as we already concluded it's a tree structure without cycles by nature.
Does the problem involve connectivity?
- Not in the strict sense of graph connectivity (e.g., connected components or paths between nodes). Here, the focus is on the depth and layout of tree nodes (directories and files).
Conclusion: Following the flowchart route for a "tree" structure, we should use Depth First Search (DFS) to explore each branch (directory/file path) fully before backtracking. This approach will help efficiently calculate the longest path by visiting all nodes (files and directories) while maintaining the count of path lengths.
Intuition
For solving this problem, the solution builds upon several observations and a straightforward approach using a stack data structure.
- Identify Levels: We can first observe that the indentation (
\t
) represents the depth or level of directories in which a file or subdirectory is located. - Simulate a Stack: As we go through the file system representation, we can simulate the nesting of directories using a stack. We push the length of each directory onto the stack when we encounter it, and if we find that the current level is less than the stack length, we pop from the stack.
- Track Files and Directories: While going through each component (file or directory), we need to check if it's a file or a directory. A file is identified by the appearance of a period (
.
) that denotes an extension. - Calculate Paths Length: We add lengths of directories in the stack to get the full path length to the current file or directory. We add 1 for each level to account for the slash (
'/'
) that would be in the actual path.
The algorithm iteratively processes the input. At each file or directory, it:
- Counts the level of indentation and moves to the name.
- Processes the name, checking if it's a directory or a file while counting its length.
- If the current level is less than the stack length, it corrects the stack by popping elements.
- If a directory is found, it pushes its length (plus the lengths of its parent directories plus slashes) onto the stack.
- If a file is found, it calculates the potential absolute path length and updates the maximum length found so far if necessary.
Finally, after processing the whole input, the maximum length found is the length of the longest absolute path to a file in the system.
Learn more about Stack and Depth-First Search patterns.
Solution Approach
The solution uses a stack to keep track of the lengths of the paths up to the current directory level. It iterates through each character of the input string to build the full absolute file paths and then calculates the length of these paths. Here's the approach broken down step by step, showcasing how the code implements the algorithm:
-
Initialization: A stack
stk
is used to keep track of the cumulative lengths of directories at different levels, and an integerans
is initialized to hold the maximum path length. -
Loop Through the Input String:
- The outer
while
loop (while i < n:
) iterates through each character in the input string. The variablei
is used to track the current index, andn
is the length of the input string.
- The outer
-
Count Indentations:
- A nested
while
loop calculates the level of indentation (ident
) for the current line by counting tab characters\t
. This level will determine the depth of the file or directory in the file system.
- A nested
-
Process File/Directory Names:
- Another
while
loop collects the name of the file or directory (cur
denotes its length). It also checks whether the current name represents a file by looking for a period (.
) which signifies an extension.
- Another
-
Managing the Stack:
- The
while len(stk) > 0 and len(stk) > ident:
loop pops elements from the stack until the stack's length is equal to the current indentation level. This simulates "exiting" directories until reaching the correct level in the hierarchy.
- The
-
Update Current Length:
- If the stack is not empty, the current name's length is updated by adding the length from the top of the stack (previous directory or root) and 1 for the slash.
-
Directory or File Logic:
- If the name is of a directory (indicated by not being a file), it is pushed onto the stack.
- If the name represents a file, the algorithm checks if the current length is greater than the previously stored maximum path length and updates
ans
if necessary.
-
Return Maximum Path Length:
- After the loop concludes,
ans
holds the maximum length of an absolute file path found in the input string, which is returned as the result.
- After the loop concludes,
The algorithm efficiently traverses the string representation of the file system and computes the required information using a single pass and a stack to manage the directory hierarchy. Mathematical steps, such as calculating the current name's length and updating the cumulative path lengths, are straightforward arithmetic operations.
The iterative approach, combined with the stack for managing the logical nesting of directories, makes the solution elegant and effective for the problem at hand.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's use a simpler example than the one provided to illustrate the solution approach step by step.
Take the following file system string representation:
"dir\n\tsubdir1\n\t\tfile.ext"
Here is what our algorithm would look like when applied to this string:
-
Initialization:
- Start with an empty stack
stk
andans = 0
to hold the maximum path length.
- Start with an empty stack
-
Loop Through the Input String:
- The string is
n=27
characters long, so we start the outer loop withi = 0
.
- The string is
-
Count Indentations:
- At the start, there are no indentations for "dir", so
ident = 0
.
- At the start, there are no indentations for "dir", so
-
Process File/Directory Names:
- Collect "dir" (
cur = 3
), which is a directory name without a'.'
.
- Collect "dir" (
-
Managing the Stack:
- The stack is empty, so we do not pop.
-
Update Current Length:
cur += 0 (stack is empty)
, socur
remains3
. We don't have a slash to add because this is the root.
-
Directory or File Logic:
- "dir" is a directory, so we push its length onto the stack,
stk = [3]
.
- "dir" is a directory, so we push its length onto the stack,
Now, i
has moved to the beginning of "subdir1"
.
-
Count Indentations (Again):
- We encounter one indentation (
\t
), soident = 1
now.
- We encounter one indentation (
-
Process File/Directory Names (Again):
- Collect "subdir1" (
cur = 7
), still no'.'
.
- Collect "subdir1" (
-
Managing the Stack (Again):
- The stack length is
1
which is equal to the currentident
, so nothing is popped from the stack.
- The stack length is
-
Update Current Length (Again):
- This time we do have a previous directory, so
cur += stk[-1] + 1
. - The new
cur = 7 (subdir1 length) + 3 (dir length) + 1 (slash) = 11
.
- This time we do have a previous directory, so
-
Directory or File Logic (Again):
- We push the length of "subdir1" onto the stack, now
stk = [3, 11]
.
- We push the length of "subdir1" onto the stack, now
Now, i
is at the beginning of "file.ext"
.
-
Count Indentations (Yet Again):
- Two indentations are encountered (
\t\t
), soident = 2
.
- Two indentations are encountered (
-
Process File/Directory Names (Yet Again):
- Collect "file.ext" (
cur = 8
), and this time we have a'.'
, so it's a file.
- Collect "file.ext" (
-
Managing the Stack (Yet Again):
- The stack length is
2
which is equal to the currentident
, so we don't pop.
- The stack length is
-
Update Current Length (Yet Again):
- Since "file.ext" is a file, we calculate its entire path length.
cur += stk[-1] + 1
. - New
cur = 8 (file.ext length) + 11 (subdir1 length) + 1 (slash) = 20
.
- Since "file.ext" is a file, we calculate its entire path length.
-
Directory or File Logic (Yet Again):
- Since it's a file, we check if
cur > ans
. It is, so we updateans = 20
.
- Since it's a file, we check if
-
Return Maximum Path Length:
- Having processed the entire string, we return
ans = 20
, which is the length of the path "dir/subdir1/file.ext".
- Having processed the entire string, we return
By following these steps, our algorithm has successfully calculated the longest absolute path to "file.ext", effectively showcasing how the stack helps keep track of each directory's cumulative path length and how we use it to construct paths to files.
Solution Implementation
1class Solution:
2 def lengthLongestPath(self, input: str) -> int:
3 index, length = 0, len(input)
4 max_length = 0 # Will store the length of the longest absolute path to a file
5 stack = [] # Use a stack to keep track of the current path length
6
7 # Iterate over the entire input string
8 while index < length:
9 level = 0
10 # Count the level of indentation to determine the depth in the directory structure
11 while input[index] == '\t':
12 level += 1
13 index += 1
14
15 current_length = 0 # Length of the current file or directory name
16 is_file = False # Flag to indicate if the current path is a file
17
18 # Iterate until the end of the current file/directory name
19 while index < length and input[index] != '\n':
20 current_length += 1
21 # If a period is found, it is a file
22 if input[index] == '.':
23 is_file = True
24 index += 1
25
26 index += 1 # Move past the newline character
27
28 # Pop from the stack until it matches the current depth level
29 while len(stack) > level:
30 stack.pop()
31
32 if stack:
33 # If stack is not empty, then add the length of the top of the stack
34 # which is the parent directory's path length, plus 1 for the '/'
35 current_length += stack[-1] + 1
36
37 # If the current path is not a file, push its length onto the stack
38 if not is_file:
39 stack.append(current_length)
40 else:
41 # If it is a file, update the maximum length if needed
42 max_length = max(max_length, current_length)
43
44 return max_length
45
1class Solution {
2 public int lengthLongestPath(String input) {
3 int index = 0; // Pointer to iterate over characters in the input string
4 int maxLength = 0; // Maximum length of file path
5 Deque<Integer> stack = new ArrayDeque<>(); // Stack to keep track of the lengths of directories
6
7 while (index < input.length()) {
8 int level = 0; // Level of the current file or directory (number of '\t' characters)
9
10 // Count the level (number of '\t')
11 while (index < input.length() && input.charAt(index) == '\t') {
12 level++;
13 index++;
14 }
15
16 int length = 0; // Current directory or file length
17 boolean isFile = false; // Flag to check if the current path is a file or directory
18
19 // Calculate the length of the current file or directory name
20 while (index < input.length() && input.charAt(index) != '\n') {
21 length++;
22 if (input.charAt(index) == '.') {
23 isFile = true; // It's a file if there is a period ('.')
24 }
25 index++;
26 }
27 index++; // Move to the next character after '\n'
28
29 // If the current level is less than the stack size,
30 // it means we have to go up the directory tree
31 while (!stack.isEmpty() && stack.size() > level) {
32 stack.pop();
33 }
34
35 // If the stack is not empty, add the length of the top directory to 'length',
36 // plus one for the '\' character.
37 if (!stack.isEmpty()) {
38 length += stack.peek() + 1;
39 }
40
41 // If it's not a file, push the length of the current directory onto the stack
42 if (!isFile) {
43 stack.push(length);
44 } else {
45 // If it's a file, update maxLength if necessary
46 maxLength = Math.max(maxLength, length);
47 }
48 }
49 return maxLength; // Return the maximum length
50 }
51}
52
1class Solution {
2public:
3 int lengthLongestPath(string input) {
4 int i = 0, n = input.size(); // Initialize the current index and get the size of the input
5 int maxLength = 0; // Variable to store the maximum length of a file path
6 stack<int> lengthStack; // Stack to store the cumulative length of directories
7
8 // Process the entire input string
9 while (i < n) {
10 int depth = 0; // Initialize the depth (level of the directory/file)
11
12 // Count the number of '\t' to determine the depth
13 while (i < n && input[i] == '\t') {
14 ++depth;
15 ++i;
16 }
17
18 int currentLength = 0; // Length of the current file/directory name
19 bool isFile = false; // Flag to detect if the current path is a file
20
21 // Iterate over the current file/directory name
22 while (i < n && input[i] != '\n') {
23 ++currentLength;
24 if (input[i] == '.') { // Check for a '.' to detect if it is a file
25 isFile = true;
26 }
27 ++i;
28 }
29
30 // Move to the next character (after '\n') for the next iteration
31 ++i;
32
33 // Pop from the stack until the stack depth is greater than the current depth
34 while (!lengthStack.empty() && lengthStack.size() > depth) {
35 lengthStack.pop();
36 }
37
38 // If there is a parent directory, add its length and a slash
39 if (!lengthStack.empty()) {
40 currentLength += lengthStack.top() + 1; // Add 1 for the separating '/' between directories
41 }
42
43 // If the path is not a file, push the current length to the stack
44 if (!isFile) {
45 lengthStack.push(currentLength);
46 } else {
47 // Update maxLength if this is a file with the longest path so far
48 maxLength = max(maxLength, currentLength);
49 }
50 }
51 return maxLength; // Return the maximum file path length found
52 }
53};
54
1// A function to find the length of the longest file path in the file system
2function lengthLongestPath(input: string): number {
3 let i = 0;
4 const n = input.length; // Get the length of the input string
5 let maxLength = 0; // Variable to store the maximum length of a file path
6 let lengthStack: number[] = []; // An array to simulate a stack for the cumulative lengths
7
8 while (i < n) {
9 let depth = 0; // Initialize the depth for the current line
10
11 // Calculate the depth by counting the number of '\t'
12 while (i < n && input[i] === '\t') {
13 depth++;
14 i++;
15 }
16
17 let currentLength = 0; // Variable to store the current file/directory name length
18 let isFile = false; // Flag to check if the current entry is a file
19
20 // Iterate over the current file/directory name
21 while (i < n && input[i] !== '\n') {
22 currentLength++;
23 if (input[i] === '.') { // A dot in the name indicates that this is a file
24 isFile = true;
25 }
26 i++;
27 }
28
29 // Move to the start of the next line
30 i++;
31
32 // Adjust the stack based on the current depth
33 while (lengthStack.length > depth) {
34 lengthStack.pop();
35 }
36
37 // If there's a parent directory, include its length and one extra for the slash
38 if (lengthStack.length > 0) {
39 currentLength += lengthStack[lengthStack.length - 1] + 1;
40 }
41
42 if (!isFile) {
43 // If it's a directory, push the current cumulative length onto the stack
44 lengthStack.push(currentLength);
45 } else {
46 // If it's a file, check if the current path is the longest one seen and update as necessary
47 maxLength = Math.max(maxLength, currentLength);
48 }
49 }
50
51 // Return the maximum length of a path to a file found in the input
52 return maxLength;
53}
54
Time and Space Complexity
Time Complexity
The time complexity of the code is O(N), where N
is the length of the input string. This is because the while loop iterates over each character in the string exactly once. The inner while loops are for counting the indentation (by tabs) and for scanning the current file/directory name, but they do not add to the overall time complexity, as they just break the input into logical segments without re-iterating over previously checked characters. Moreover, the stack operations such as push (append) and pop operations take O(1) time per operation. Since the number of operations is bounded by N
(you can’t push or pop more than once per character in the string), the stack operations also do not exceed O(N) time complexity.
Space Complexity
The space complexity of the code is O(D), where D
is the maximum depth of files/subdirectories. This is because the stack stk
only stores information about the current path, and this path cannot be deeper than the maximum depth. In the worst case, where the input string is a single deep path, we have to store each part of the path on the stack (the additional cur
does not count towards the space complexity since it is an integer and does not grow with input size).
Learn more about how to find time and space complexity quickly using problem constraints.
A person thinks of a number between 1 and 1000. You may ask any number questions to them, provided that the question can be answered with either "yes" or "no".
What is the minimum number of questions you needed to ask so that you are guaranteed to know the number that the person is thinking?
Recommended Readings
Stack Intro Imagine you have a pile of books on your desk If you want to add a new book you place it on top If you want to read a book you take it from the top And if you simply want to see which book is on the top you
https algomonster s3 us east 2 amazonaws com cover_photos dfs svg Depth First Search Prereqs Recursion Review problems recursion_intro Trees problems tree_intro With a solid understanding of recursion under our belts we are now ready to tackle one of the most useful techniques in coding interviews Depth First Search DFS
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Want a Structured Path to Master System Design Too? Don’t Miss This!