{x}
blog image

Longest Absolute File Path

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.

Solution Explanation for Longest Absolute File Path

This problem involves parsing a string representation of a file system and finding the length of the longest absolute path to a file. The input string uses tabs to represent levels of nesting and newlines to separate entries.

Approach

The optimal approach uses a stack to keep track of the lengths of paths at different levels of the directory structure. The algorithm iterates through the input string, identifying the level of each entry (based on the number of leading tabs) and whether it's a file or directory.

  1. Initialization: A stack stk is used to store the lengths of directory paths. ans variable keeps track of the maximum length encountered.

  2. Iteration: The algorithm iterates through the input string character by character.

  3. Level Detection: It counts the leading tabs to determine the nesting level.

  4. Entry Processing: It extracts the name of the current entry (file or directory). If the entry contains a ".", it's a file; otherwise, it's a directory.

  5. Stack Management:

    • If the current level is shallower than the stack's depth, elements are popped from the stack until the stack's depth matches the current level. This simulates moving up the directory tree.
    • If it's a directory, its length is pushed onto the stack.
    • If it's a file, its length is added to the top of the stack (representing the parent directory path) plus 1 (for the '/' separator), and the result is compared with ans to update the maximum path length.

  6. Result: Finally, ans (the maximum path length) is returned.

Time and Space Complexity

  • Time Complexity: O(N), where N is the length of the input string. The algorithm iterates through the string once. Stack operations (push and pop) take constant time on average.

  • Space Complexity: O(D), where D is the maximum depth of the directory structure. In the worst case, the stack can hold at most D entries, one for each level of nesting.

Code Explanation (Python)

class Solution:
    def lengthLongestPath(self, input: str) -> int:
        i, n = 0, len(input)
        ans = 0
        stk = []  # Stack to store path lengths
        while i < n:
            ident = 0
            while input[i] == '\t':  # Count leading tabs for level
                ident += 1
                i += 1
 
            cur, isFile = 0, False  # Length of current entry, is it a file?
            while i < n and input[i] != '\n':
                cur += 1
                if input[i] == '.':
                    isFile = True  # Detect file by '.'
                i += 1
            i += 1  # Move past newline
 
            while len(stk) > 0 and len(stk) > ident: # Adjust stack depth
                stk.pop()
 
            if len(stk) > 0:
                cur += stk[-1] + 1  # Add parent path length and '/'
 
            if not isFile:
                stk.append(cur)  # Push directory length
            else:
                ans = max(ans, cur)  # Update max file path length
 
        return ans

The code in other languages (Java, C++, Go) follows the same logic, using appropriate data structures (stack) and syntax for each language. The core algorithm remains consistent across all implementations.