Longest Absolute File Path - Leetcode Solution

The Longest Absolute File Path problem on LeetCode is a popular problem that requires you to find the length of the longest absolute file path in a given string input. The file path is represented by a string that uses "\t" characters to indicate the level of nesting of a file or folder.

For example, the input "dir\n\tsubdir1\n\tsubdir2\n\t\tfile.ext" represents a file structure where "dir" is the root folder, "subdir1" and "subdir2" are its subfolders, and "file.ext" is a file within "subdir2". The "\n" character separates the elements, and "\t" indicates the nesting level.

To solve this problem, we can use a stack to keep track of the current nesting level and the lengths of the directories we've encountered so far. We can iterate through the input string, splitting it by "\n" characters, and then process each element of the path.

Here's an outline of the solution:

1. Split the input string by "\n" characters to get a list of file and directory names.
2. Create a stack to keep track of the current nesting level and the lengths of the directories we've encountered so far.
3. Iterate through the list of paths, processing each element as follows: a. Count the number of "\t" characters at the beginning of the path to determine the nesting level (this is the length of the stack). b. Remove any elements from the stack that have a nesting level greater than the current level (i.e. pop the stack until the length equals the current nesting level). c. Get the length of the current element (i.e. the length of the string minus the number of "\t" characters). d. If the current element is a file (i.e. contains a "." character), calculate the length of the absolute file path by adding up the lengths of the directories in the stack and the length of the file. If this length is greater than the current maximum, update the maximum length. e. Otherwise, push the length of the current element onto the stack (i.e. add the length of the directory to the list of directory lengths).
4. Return the maximum length of an absolute file path.

Here's the Python code for the solution:

def lengthLongestPath(input: str) -> int:
    max_len = 0
    stack = [0]  # stack stores the current directory lengths
    
    for path in input.split('\n'):
        # count the number of '\t' characters to determine the nesting level
        level = path.count('\t')
        
        # pop the stack until the length equals the current nesting level
        while level + 1 < len(stack):
            stack.pop()
        
        # get the length of the current element 
        curr_len = len(path) - level
        
        # if the current element is a file, calculate the length of the absolute file path
        if '.' in path:
            max_len = max(max_len, stack[-1] + curr_len)
        
        # otherwise, add the length of the directory to the stack
        else:
            stack.append(stack[-1] + curr_len + 1)  # add 1 for the separator
        
    return max_len

1