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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Longest Absolute File Path

Difficulty: Medium

Problem Description

Given a string input representing a file system with directories and files, return the length of the longest absolute path to a file. The input format uses new-line and tab characters to represent the structure of directories and files. If there are no files, return 0.

Key Insights

  • Each directory and file is represented by its level of indentation, determined by the number of tab characters.
  • The absolute path to a file is constructed by concatenating directory names with '/'.
  • Only paths that end with a file name (containing a '.') are considered valid for finding the longest path.
  • A stack can be used to keep track of the current path lengths for directories as we parse the input.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the input string. Each character is processed once. Space Complexity: O(n), in the worst case, if all components are directories (i.e., all paths are stored in the stack).

Solution

To solve the problem, we can utilize a stack to track the lengths of paths to the current directory level as we iterate through the input string. The algorithm proceeds as follows:

  1. Split the input string by new lines to get each component.
  2. For each component, determine its level by counting the leading tab characters.
  3. Depending on whether the component is a file or directory, update the stack and calculate the potential longest path.
  4. Maintain a variable to track the maximum length of any file path encountered.

Code Solutions

def lengthLongestPath(input: str) -> int:
    max_length = 0
    path_lengths = {0: 0}  # Maps level to the length of the path up to that level
    
    for line in input.splitlines():
        # Count the depth (level) of the current component
        level = line.count('\t')
        # Remove the tabs to get the actual name
        name = line[level:]
        
        if '.' in name:  # It's a file
            max_length = max(max_length, path_lengths[level] + len(name))
        else:  # It's a directory
            path_lengths[level + 1] = path_lengths[level] + len(name) + 1  # +1 for the '/' separator
    
    return max_length
← Back to All Questions