algoadvance

Leetcode Problem 388: Longest Absolute File Path

Suppose we have a file system represented in the following string format:

The string "dir\n\tsubdir1\n\tsubdir2\n\t\tfile.ext" represents:

dir
    subdir1
    subdir2
        file.ext

The directory dir contains an empty subdirectory subdir1 and a subdirectory subdir2 containing a file file.ext.

We need to find the length of the longest absolute path to a file within our file system.

Note:

• The name of a file contains at least one . and an extension.
• The name of a directory or a file will not contain any \n, \t, and it will not be empty.
• The string "dir"/"subdir2" is a valid input.
• Every directory`s string contains the name of the directory and will be followed by a new line character.
• A file does not contain the tab character \t.

Clarifying Questions

1. What is the expected input format?
   • The input is a single string where the hierarchy is represented using \n for new lines and \t for indentation levels.
2. What is the expected output?
   • The output is an integer representing the length of the longest absolute path to any file in the system.
3. Could there be multiple files, or is there always exactly one?
   • There can be multiple files or none.
4. Should we consider only files that have an extension .ext, or any file with a . in its name?
   • Any file with a . in its name.
5. What should we return if there are no files?
   • If there are no files, return 0.

Strategy

1. Split the input string by \n to process each line separately.
2. Use a dictionary to store the maximum length of paths seen so far at each depth level.
3. Traverse the list of processed lines:
   • For each line, determine its depth based on the number of leading \t.
   • Calculate the length of the current path and update the dictionary.
   • If the current line represents a file (contains .), update the maximum length if the current path length is greater.
4. Return the maximum length found.

Code

def lengthLongestPath(input: str) -> int:
    # Split the input by newline to get each component in the hierarchy
    lines = input.split('\n')
    
    # Dictionary to store current path length at each depth
    path_length = {0: 0}
    max_length = 0
    
    for line in lines:
        # Count the depth by number of leading '\t'
        depth = line.count('\t')
        # Strip the leading '\t' characters to get the name of the directory or file
        name = line.lstrip('\t')
        
        # If it's a file, check and update max_length
        if '.' in name:
            max_length = max(max_length, path_length[depth] + len(name))
        else:
            # If it's a directory, update the path length for the next level
            path_length[depth + 1] = path_length[depth] + len(name) + 1
    
    return max_length

Time Complexity

• Time Complexity: O(n) - Each line of the input string is processed once, where n is the total number of characters in the input string.
• Space Complexity: O(d) - We use a dictionary to store the current path length at each depth level, where d is the maximum depth of the directory structure.

This solution efficiently traverses the hierarchical structure represented in the input string and calculates the longest absolute file path, considering memory and computational constraints.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?