Longest Absolute File Path

MEDIUM

Description

[Fetch error]

Approaches

Checkout 2 different approaches to solve Longest Absolute File Path. Click on different approaches to view the approach and algorithm in detail.

Brute Force Path Reconstruction

This approach iterates through each entry in the file system. When a file is found, it reconstructs its entire absolute path by searching backwards for its parent directories, level by level, until it reaches the root. The length of this reconstructed path is then calculated. This process is repeated for every file in the system.

Algorithm

Split the input string by the newline character \n to get an array of all file/directory entries.
Initialize a variable maxLength to 0.
Iterate through each entry s with its index i in the array.
If the entry s does not contain a . (i.e., it's a directory), skip it.
If it is a file, determine its depth currentLevel by counting the leading \t characters.
Calculate the current path length, starting with the length of the file's name.
Iterate backwards from index i-1 down to 0 to find its ancestors.
In the backward scan, look for an entry whose depth is exactly currentLevel - 1. This is the parent.
Once the parent is found, add its name length plus 1 (for the / separator) to the current path length.
Decrement currentLevel and continue the backward scan to find the grandparent, and so on, until the root (level 0) is processed.
After building the full path length for the current file, update maxLength = max(maxLength, currentPathLength).
Return maxLength after checking all entries.

The core idea is to treat the problem as a search task. For every line that represents a file, we initiate a backward search through the preceding lines to find its hierarchical parents. The depth of each entry, determined by the number of tab characters, guides this search.

Here is the algorithm:

Split the input string by the newline character \n to get an array of all file/directory entries.
Initialize a variable maxLength to 0.
Iterate through each entry s with its index i in the array.
If the entry s does not contain a . (i.e., it's a directory), skip it.
If it is a file, determine its depth currentLevel by counting the leading \t characters.
Calculate the current path length, starting with the length of the file's name.
Iterate backwards from index i-1 down to 0 to find its ancestors.
In the backward scan, look for an entry whose depth is exactly currentLevel - 1. This is the parent.
Once the parent is found, add its name length plus 1 (for the / separator) to the current path length.
Decrement currentLevel and continue the backward scan to find the grandparent, and so on, until the root (level 0) is processed.
After building the full path length for the current file, update maxLength = max(maxLength, currentPathLength).
Return maxLength after checking all entries.

class Solution {
    public int lengthLongestPath(String input) {
        String[] paths = input.split("\n");
        int maxLength = 0;

        for (int i = 0; i < paths.length; i++) {
            String currentPathStr = paths[i];
            // We only care about paths to files.
            if (!currentPathStr.contains(".")) {
                continue;
            }

            int currentLevel = getLevel(currentPathStr);
            // Length of the file name itself.
            int currentLength = currentPathStr.length() - currentLevel;
            int parentLevel = currentLevel - 1;

            // Search backwards for parent directories.
            for (int j = i - 1; j >= 0 && parentLevel >= 0; j--) {
                String potentialParent = paths[j];
                if (getLevel(potentialParent) == parentLevel) {
                    // Add parent's name length + 1 for the '/'.
                    currentLength += (potentialParent.length() - parentLevel) + 1;
                    parentLevel--;
                }
            }
            maxLength = Math.max(maxLength, currentLength);
        }
        return maxLength;
    }

    // Helper to count the level (number of tabs).
    private int getLevel(String s) {
        return s.lastIndexOf('\t') + 1;
    }
}

Complexity Analysis

Time Complexity: O(L^2), where L is the number of lines (files/directories). For each file (of which there can be up to L), we may scan backwards through all L previous lines.Space Complexity: O(N), where N is the length of the input string. This space is required to store the array of strings after splitting the input.

Pros and Cons

Pros:

Conceptually straightforward, as it directly mimics the process of building a path for each file.
Does not require complex data structures, relying only on array indexing and loops.

Cons:

Highly inefficient due to redundant computations. The path for a common directory like dir is recalculated for every file under it.
The nested loop structure leads to poor time complexity, making it unsuitable for large inputs.

Code Solutions

Checking out 3 solutions in different languages for Longest Absolute File Path. Click on different languages to view the code.

class Solution {
public
  int lengthLongestPath(String input) {
    int i = 0;
    int n = input.length();
    int ans = 0;
    Deque<Integer> stack = new ArrayDeque<>();
    while (i < n) {
      int ident = 0;
      for (; input.charAt(i) == '\t'; i++) {
        ident++;
      }
      int cur = 0;
      boolean isFile = false;
      for (; i < n && input.charAt(i) != '\n'; i++) {
        cur++;
        if (input.charAt(i) == '.') {
          isFile = true;
        }
      }
      i++;

Video Solution

Watch the video walkthrough for Longest Absolute File Path

Algorithms:

Depth-First Search

Data Structures:

StringStack