388. Longest Absolute File Path

MediumStackDepth-First SearchString
Leetcode Link

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:

1"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.

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:

  1. Counts the level of indentation and moves to the name.
  2. Processes the name, checking if it's a directory or a file while counting its length.
  3. If the current level is less than the stack length, it corrects the stack by popping elements.
  4. If a directory is found, it pushes its length (plus the lengths of its parent directories plus slashes) onto the stack.
  5. 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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

How would you design a stack which has a function min that returns the minimum element in the stack, in addition to push and pop? All push, pop, min should have running time O(1).

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:

  1. Initialization: A stack stk is used to keep track of the cumulative lengths of directories at different levels, and an integer ans is initialized to hold the maximum path length.

  2. Loop Through the Input String:

    • The outer while loop (while i < n:) iterates through each character in the input string. The variable i is used to track the current index, and n is the length of the input string.

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

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

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

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

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

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

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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

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?

Example 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:

1"dir\n\tsubdir1\n\t\tfile.ext"

Here is what our algorithm would look like when applied to this string:

  1. Initialization:

    • Start with an empty stack stk and ans = 0 to hold the maximum path length.

  2. Loop Through the Input String:

    • The string is n=27 characters long, so we start the outer loop with i = 0.

  3. Count Indentations:

    • At the start, there are no indentations for "dir", so ident = 0.

  4. Process File/Directory Names:

    • Collect "dir" (cur = 3), which is a directory name without a '.'.

  5. Managing the Stack:

    • The stack is empty, so we do not pop.

  6. Update Current Length:

    • cur += 0 (stack is empty), so cur remains 3. We don't have a slash to add because this is the root.

  7. Directory or File Logic:

    • "dir" is a directory, so we push its length onto the stack, stk = [3].

Now, i has moved to the beginning of "subdir1".

  1. Count Indentations (Again):

    • We encounter one indentation (\t), so ident = 1 now.

  2. Process File/Directory Names (Again):

    • Collect "subdir1" (cur = 7), still no '.'.

  3. Managing the Stack (Again):

    • The stack length is 1 which is equal to the current ident, so nothing is popped from the stack.

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

  5. Directory or File Logic (Again):

    • We push the length of "subdir1" onto the stack, now stk = [3, 11].

Now, i is at the beginning of "file.ext".

  1. Count Indentations (Yet Again):

    • Two indentations are encountered (\t\t), so ident = 2.

  2. Process File/Directory Names (Yet Again):

    • Collect "file.ext" (cur = 8), and this time we have a '.', so it's a file.

  3. Managing the Stack (Yet Again):

    • The stack length is 2 which is equal to the current ident, so we don't pop.

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

  5. Directory or File Logic (Yet Again):

    • Since it's a file, we check if cur > ans. It is, so we update ans = 20.

  6. Return Maximum Path Length:

    • Having processed the entire string, we return ans = 20, which is the length of the path "dir/subdir1/file.ext".

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
Not Sure What to Study? Take the 2-min Quiz：

What's the output of running the following function using input 56?

1KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13    def dfs(path, res):
14        if len(path) == len(digits):
15            res.append(''.join(path))
16            return
17
18        next_number = digits[len(path)]
19        for letter in KEYBOARD[next_number]:
20            path.append(letter)
21            dfs(path, res)
22            path.pop()
23
24    res = []
25    dfs([], res)
26    return res
27
1private static final Map<Character, char[]> KEYBOARD = Map.of(
2    '2', "abc".toCharArray(),
3    '3', "def".toCharArray(),
4    '4', "ghi".toCharArray(),
5    '5', "jkl".toCharArray(),
6    '6', "mno".toCharArray(),
7    '7', "pqrs".toCharArray(),
8    '8', "tuv".toCharArray(),
9    '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13    List<String> res = new ArrayList<>();
14    dfs(new StringBuilder(), res, digits.toCharArray());
15    return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19    if (path.length() == digits.length) {
20        res.add(path.toString());
21        return;
22    }
23    char next_digit = digits[path.length()];
24    for (char letter : KEYBOARD.get(next_digit)) {
25        path.append(letter);
26        dfs(path, res, digits);
27        path.deleteCharAt(path.length() - 1);
28    }
29}
30
1const KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13    let res = [];
14    dfs(digits, [], res);
15    return res;
16}
17
18function dfs(digits, path, res) {
19    if (path.length === digits.length) {
20        res.push(path.join(''));
21        return;
22    }
23    let next_number = digits.charAt(path.length);
24    for (let letter of KEYBOARD[next_number]) {
25        path.push(letter);
26        dfs(digits, path, res);
27        path.pop();
28    }
29}
30

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.

Fast Track Your Learning with Our Quick Skills Quiz:

Which type of traversal does breadth first search do?

Recommended Readings

Stack Intro

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

DFS Fundamentals

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 - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫