Scale Engineer

Longest Absolute File Path

Med
#0375Time: 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: 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.
Algorithms
Depth-First Search
Data structures
StringStack

Prompt

[Fetch error]

Approaches

2 approaches with complexity analysis and trade-offs.

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

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

Walkthrough

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:

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

Time

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

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.

Trade-offs

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.

Solutions

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 walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem