NUHMAN.com

📘 Problem Statement

Given a string input representing a file system where directories and files are separated by \n, return the length of the longest absolute path to a file in the system. The file or directory names have no spaces in them and they follow the rules below:

• A directory is separated by a single / and a file is a file that contains a . in its name.
• The string contains a hierarchical structure, with indentation using tabs (\t), where each tab represents one level of depth in the directory structure.

📚 Example:

python

Input:
input = "dir\n\tsubdir1\n\tsubdir2\n\t\tfile.ext"
Output:
15
Explanation:
The longest path is "dir/subdir2/file.ext", which has length 15.
python

Input:
input = "dir\n\tsubdir1\n\tsubdir2\n\t\tfile"
Output:
9
Explanation:
There is no file in "dir/subdir2", so the longest path is "dir/subdir1", which has length 9.

🧠 Key Insight

This problem involves simulating a file system structure, and the goal is to find the longest file path by considering the file names and directory names, accounting for nested directories (represented by \t or tabs).

We can solve this efficiently by using a stack to keep track of the lengths of directory paths as we encounter them.

💡 Approach

1. Iterate Through the Input:

• Traverse the string input and use a stack to simulate the directory structure.

1. Track Depth:

• The depth of each directory is determined by the number of leading tabs (\t).

1. Handle File or Directory:

• For each directory or file, determine its depth and calculate the path length.
• If it's a file (indicated by a .), we update the maximum path length.

1. Return the Result:

• After processing all lines, return the maximum length found.

🐍 Python Code

python

class Solution:
    def lengthLongestPath(self, input: str) -> int:
        stack = []
        max_length = 0
        for line in input.split("\n"):
            # Count the number of tabs
            depth = line.count("\t")
            # Strip the leading tabs to get the actual name
            name = line.lstrip("\t")
            
            # Adjust the stack size to the current depth
            if depth < len(stack):
                stack = stack[:depth]
            
            # If it's a file, update max_length
            if "." in name:
                max_length = max(max_length, sum(len(part) for part in stack) + len(name))
            else:
                # If it's a directory, add it to the stack
                stack.append(name)
        
        return max_length

🔍 Step-by-Step Explanation

1. Split the Input by Line

python

for line in input.split("\n"):

• The input is split by newline characters (\n), which allows us to process each directory/file entry separately.
• Each line can be a directory or a file, and its structure is defined by how many tabs it contains.

2. Count the Depth of Each Line

python

depth = line.count("\t")

• The number of leading tabs (\t) represents the depth of the current directory in the file system hierarchy.
• This depth is crucial for correctly building the path to the file or directory.

3. Strip Tabs and Get the Actual Name

python

name = line.lstrip("\t")

• After counting the tabs, we strip the leading tabs to get the name of the directory or file.

4. Adjust the Stack Size Based on Depth

python

if depth < len(stack):
    stack = stack[:depth]

• We use a stack to keep track of the directories as we encounter them.
• If we encounter a directory at a higher depth, we append it to the stack.
• If we encounter a directory at a lower depth (meaning we’ve exited a subdirectory), we trim the stack to the appropriate depth.

5. Check If It’s a File or Directory

python

if "." in name:
    max_length = max(max_length, sum(len(part) for part in stack) + len(name))

• If the name contains a . (dot), it means it's a file. We calculate the total length of the path by adding the lengths of all directory names in the stack and the current file's name.
• We then update the maximum length if this path is longer than any previously found.

6. Handle Directories

python

else:
    stack.append(name)

• If it’s not a file (i.e., a directory), we add the directory name to the stack.

7. Return the Maximum Path Length

python

return max_length

• After processing all lines, we return the max_length, which holds the longest absolute path to a file.

💡 Example Walkthrough

Example 1:

python

Input:
input = "dir\n\tsubdir1\n\tsubdir2\n\t\tfile.ext"
Output:
15

1. First Line (dir):

• Depth = 0, name = dir
• Add dir to the stack.

1. Second Line (\tsubdir1):

• Depth = 1, name = subdir1
• Add subdir1 to the stack.

1. Third Line (\tsubdir2):

• Depth = 1, name = subdir2
• Adjust stack to depth 1, then add subdir2.

1. Fourth Line (\t\tfile.ext):

• Depth = 2, name = file.ext
• File found. Calculate the path length: len("dir") + len("subdir2") + len("file.ext") = 15.
• Update max_length to 15.

1. Return: The longest path is dir/subdir2/file.ext with length 15.

Example 2:

python

Input:
input = "dir\n\tsubdir1\n\tsubdir2\n\t\tfile"
Output:
9

1. First Line (dir):

• Depth = 0, name = dir
• Add dir to the stack.

1. Second Line (\tsubdir1):

• Depth = 1, name = subdir1
• Add subdir1 to the stack.

1. Third Line (\tsubdir2):

• Depth = 1, name = subdir2
• Adjust stack to depth 1, then add subdir2.

1. Fourth Line (\t\tfile):

• Depth = 2, name = file
• File found. Calculate the path length: len("dir") + len("subdir1") + len("file") = 9.
• Update max_length to 9.

1. Return: The longest path is dir/subdir1/file with length 9.

⏱️ Time & Space Complexity

MetricComplexityTime ComplexityO(n)Space ComplexityO(n)

• Time Complexity:
• We traverse the input string line by line and perform constant-time operations for each line. Thus, the time complexity is O(n), where n is the length of the string.
• Space Complexity:
• We use a stack to store the current path and directory names, which can have at most n elements in the worst case. Therefore, the space complexity is O(n).

🧵 Final Thoughts

LeetCode 388 is a useful problem for practicing path construction in hierarchical data. By using a stack to track the current path and adjusting it according to the depth of directories, we can efficiently compute the longest absolute file path. This solution offers both clarity and efficiency, making it a great example of using a stack to manage nested data structures.