We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Longest Absolute File Path

Number: 388

Difficulty: Medium

Paid? No

Companies: Meta, Google, Amazon, Apple

Problem Description

Given a string that represents a file system in a serialized manner (using newline and tab characters to indicate directory depth), compute the length of the longest absolute path to any file in the system. A file is identified by the presence of a dot in its name. If no file exists, return 0.

Key Insights

  • Split the input by newline characters to process each file or directory.
  • The number of leading tab characters indicates the depth (or level) in the file system hierarchy.
  • Use a hash map or stack to keep track of the current cumulative length of the path at each level.
  • For directories, update the cumulative length (including the '/' separator).
  • For files (line contains a '.'), calculate the total path length and update the maximum if it is larger.
  • Return the maximum path length found; if no file exists, return 0.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the input string.
Space Complexity: O(n), required for storing the cumulative lengths for each directory level.

Solution

The approach is to iterate through each line representing a file or directory. First, determine the depth by counting the tab characters. Then, compute the length of the file or directory name by stripping these tabs. Maintain a mapping from depth to the total path length at that depth. For a directory, update the mapping by adding the current directory’s length to the total length of its parent level plus one for the '/' separator. When a file is encountered (detected by the presence of a dot), calculate its total absolute path length and compare it to the currently recorded maximum length. This approach efficiently processes the file system in one pass.

Code Solutions

# Python solution for Longest Absolute File Path

class Solution:
    def lengthLongestPath(self, input: str) -> int:
        # Dictionary to hold cumulative lengths for each depth level
        path_length = {0: 0}  # base level (depth 0) has length 0
        max_length = 0
        
        # Split the string by newline to process each file/directory
        for line in input.split('\n'):
            # Count the number of '\t' to determine current depth
            depth = line.count('\t')
            # Remove the tabs to get the actual name of file or directory
            name = line.lstrip('\t')
            if '.' in name:
                # It's a file, calculate its full length
                current_length = path_length[depth] + len(name)
                max_length = max(max_length, current_length)
            else:
                # It's a directory, update the cumulative length including '/'
                path_length[depth + 1] = path_length[depth] + len(name) + 1  # +1 for '/'
        
        return max_length

# Example usage:
# sol = Solution()
# print(sol.lengthLongestPath("dir\n\tsubdir1\n\tsubdir2\n\t\tfile.ext"))  # Output: 20
← Back to All Questions