coderz.py

Problem Statement (Asked By Google)

A file system can be represented using a string, where:

• Directories and subdirectories are separated by \n (new lines).
• Levels are indicated using tabs (\t).

For example, the string:

"dir\n\tsubdir1\n\tsubdir2\n\t\tfile.ext"

Represents:

dir  
    subdir1  
    subdir2  
        file.ext  

The root directory dir contains:

• subdir1 (empty)
• subdir2 containing the file file.ext

Another example:

"dir\n\tsubdir1\n\t\tfile1.ext\n\t\tsubsubdir1\n\tsubdir2\n\t\tsubsubdir2\n\t\t\tfile2.ext"

Represents:

dir  
    subdir1  
        file1.ext  
        subsubdir1  
    subdir2  
        subsubdir2  
            file2.ext 

• The root directory dir contains:
  • subdir1 with:
    • File file1.ext
    • Subdirectory subsubdir1 (empty)
  • subdir2 with:
    • Subdirectory subsubdir2 containing file file2.ext

Objective:

Find the length of the longest absolute path to a file within the abstracted file system. The length is measured in characters.

For the second example, the longest path is:

"dir/subdir2/subsubdir2/file2.ext"

• Its length is 32 characters (excluding quotes).

Notes:

• A file name always contains a period (.) for the extension.
• Directory names do not contain periods.
• If there are no files, return 0.

Problem link: https://leetcode.com/problems/longest-absolute-file-path/

Disclaimer: Try solving the problem on your own first! Use this solution only as a reference to learn and improve.

---

Explanation:

We can break the problem into two key steps:

Step 1: Parsing the File System

Given a string representation of the file system, we aim to parse it into a structured form, such as a tree or dictionary.

For example, given:

dir\n\tsubdir1\n\t\tfile1.ext\n\t\tsubsubdir1\n\tsubdir2\n\t\tsubsubdir2\n\t\t\tfile2.ext

We want a structure like this:

dir
 ├── subdir1
 │   ├── file1.ext
 │   └── subsubdir1
 └── subdir2
     └── subsubdir2
         └── file2.ext

To achieve this:

1. Split the string by newline (\n), so each line represents a file or directory.
2. Track indentation (represented by \t) to determine the directory hierarchy.
3. Use a stack to maintain the current path. Each element’s level corresponds to its depth.
4. If a line represents a file (contains a dot .), record its absolute path length.
5. If it’s a directory, push it onto the stack.

Step 2: Computing the Longest Path

• Keep track of the lengths of directories using the stack.
• When encountering a file, compute its absolute path length by summing the lengths in the stack.
• Update the longest path length if the current path is longer.

This approach ensures we only traverse the string once, achieving O(n) time complexity, where n is the length of the input string.

Full Java Implementation:

import java.util.Stack;

public class LongestAbsolutePath {
    
    public static int longestAbsolutePath(String input) {
        // Stack stores the length of each directory level
        Stack<Integer> stack = new Stack<>();
        stack.push(0); // Base length for the root directory
        int maxLength = 0;

        // Split the input into lines
        String[] lines = input.split("\n");
        
        for (String line : lines) {
            // Count number of tabs (depth)
            int level = line.lastIndexOf("\t") + 1;

            // Remove tabs to get the actual name
            String name = line.substring(level);
            
            // Adjust the stack to the current directory level
            while (stack.size() > level + 1) {
                stack.pop();
            }

            // Get the length of the current path
            int length = stack.peek() + name.length() + 1; // +1 for '/'

            if (name.contains(".")) {
                // It's a file, check if it's the longest path
                maxLength = Math.max(maxLength, length - 1); // -1 to remove trailing '/'
            } else {
                // It's a directory, store length for deeper levels
                stack.push(length);
            }
        }
        return maxLength;
    }

    public static void main(String[] args) {
        String input = "dir\n\tsubdir1\n\t\tfile1.ext\n\t\tsubsubdir1\n\tsubdir2\n\t\tsubsubdir2\n\t\t\tfile2.ext";
        System.out.println(longestAbsolutePath(input)); // Output: 32
    }
}

Explanation of Java Code:

Step 1: Parsing the File System

• String[] lines = input.split("\n"): Splits the string into directories and files.
• int level = line.lastIndexOf("\t") + 1: Counts the number of tabs to determine the depth.
• String name = line.substring(level): Gets the actual directory or file name.

Step 2: Tracking Path Lengths

• Stack Usage:
  • Push directory lengths onto the stack.
  • Pop when going back up to a parent directory.
• Path Length Calculation:
  • Add current directory length plus 1 (for the /).
  • If it’s a file, update the longest path length.

Complexity Analysis:

1. Time Complexity: O(n)
   • We only traverse the input string once.
2. Space Complexity: O(n) in the worst case for the stack (deeply nested directories).

Example Walkthrough:

For the input:

dir
    subdir1
        file1.ext
        subsubdir1
    subdir2
        subsubdir2
            file2.ext

Stack Operations:

1. dir: push length.
2. subdir1: push length.
3. file1.ext: compute full path length.
4. subdir2: pop up to dir, push length.
5. file2.ext: compute full path length.

The longest path is:

dir/subdir2/subsubdir2/file2.ext

Length: 32 characters.

This solution uses Stack and String operations to compute the longest absolute path efficiently.

---

Did this solution help you understand the concept better? Let me know your thoughts in the comments below! Don’t forget to follow us on Instagram @coderz.py for more DSA tips and solutions to ace your coding interviews.