# Longest Absolute File Path
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/longest-absolute-file-path)
Canonical: https://scaleengineer.com/dsa/problems/longest-absolute-file-path
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search)
**Data structures:** String, Stack
---
## Problem
\[Fetch error\]

# Approaches
## 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.
**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.
**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.
### Explanation
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.

```java
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;
    }
}
```
### 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.

## Single Pass with Depth Tracking
A much more efficient approach is to traverse the file system entries in a single pass. We use an auxiliary data structure (like an array or a hash map) to keep track of the path length at each depth level. When we process an entry at a certain level, we can instantly find the length of its parent's path and extend it, avoiding any recalculation. This is analogous to a pre-order traversal of the file system tree.
**Time:** O(N), where N is the length of the input string. The `split` operation takes O(N), and the loop iterates through each line once. The work inside the loop is effectively constant time on average per character, leading to a total time proportional to N. · **Space:** O(D), where D is the maximum depth of the file system. This is for the `pathLengths` array. In the worst case, D can be O(L) where L is the number of lines.
**Pros:** Optimal time complexity of O(N).; Efficiently calculates lengths without redundant work by processing each entry only once.; Handles the file system structure elegantly using a depth-based state.
**Cons:** Requires an auxiliary data structure to maintain state across levels.; The logic for updating path lengths based on levels needs to be handled carefully to be correct.
### Explanation
This optimized approach processes the file system hierarchy linearly. It maintains an array where the index corresponds to a depth level, and the value is the length of the path up to that depth. As we iterate through each line, we determine its level, find the length of its parent's path from the array, and calculate the current path's length. This avoids the expensive backward search of the brute-force method.

Here is the algorithm:
1. Initialize `maxLength = 0`.
2. Create an array, `pathLengths`, to store the length of the path at each level. `pathLengths[level + 1]` will store the length of the path to the directory at `level`, including the trailing slash.
3. Initialize `pathLengths[0] = 0`, representing the length before the root.
4. Split the input string by `\n` to get all entries.
5. Iterate through each entry `s`:
    a. Determine its `level` by finding the last index of `\t` (`s.lastIndexOf('\t') + 1`).
    b. Calculate the length of the entry's name: `nameLength = s.length() - level`.
    c. Retrieve the parent's path length from `pathLengths[level]`.
    d. Calculate the current path length: `currentPathLength = pathLengths[level] + nameLength`.
    e. If the entry `s` is a file (contains `.`), it's a complete path. Update `maxLength = max(maxLength, currentPathLength)`.
    f. If the entry `s` is a directory, update the `pathLengths` array for the next level. The length stored for the next level will be the current path length plus 1 for the separator slash: `pathLengths[level + 1] = currentPathLength + 1`.
6. Return `maxLength`.

```java
class Solution {
    public int lengthLongestPath(String input) {
        String[] paths = input.split("\n");
        // pathLengths[i] stores the length of the path to the directory at level i-1
        // including the trailing slash.
        int[] pathLengths = new int[paths.length + 1];
        int maxLength = 0;

        for (String path : paths) {
            // Determine the level (depth) of the current file/directory.
            int level = path.lastIndexOf('\t') + 1;

            // Get the length of the path to the parent directory.
            int parentPathLength = pathLengths[level];

            // Calculate the length of the current file/directory name.
            int nameLength = path.length() - level;

            // Calculate the length of the absolute path to the current item.
            int currentLength = parentPathLength + nameLength;

            if (path.contains(".")) {
                // If it's a file, we have a full path. Update max length.
                // The parentPathLength already includes the necessary slashes.
                maxLength = Math.max(maxLength, currentLength);
            } else {
                // If it's a directory, store its path length for its children to use.
                // Add 1 for the trailing '/'.
                pathLengths[level + 1] = currentLength + 1;
            }
        }
        return maxLength;
    }
}
```
### Algorithm
1. Initialize `maxLength = 0`.
2. Create an array, `pathLengths`, to store the length of the path at each level. `pathLengths[level + 1]` will store the length of the path to the directory at `level`, including the trailing slash.
3. Initialize `pathLengths[0] = 0`, representing the length before the root.
4. Split the input string by `\n` to get all entries.
5. Iterate through each entry `s`:
    a. Determine its `level` by finding the last index of `\t` (`s.lastIndexOf('\t') + 1`).
    b. Calculate the length of the entry's name: `nameLength = s.length() - level`.
    c. Retrieve the parent's path length from `pathLengths[level]`.
    d. Calculate the current path length: `currentPathLength = pathLengths[level] + nameLength`.
    e. If the entry `s` is a file (contains `.`), it's a complete path. Update `maxLength = max(maxLength, currentPathLength)`.
    f. If the entry `s` is a directory, update the `pathLengths` array for the next level. The length stored for the next level will be the current path length plus 1 for the separator slash: `pathLengths[level + 1] = currentPathLength + 1`.
6. Return `maxLength`.

# Solutions
### Java

```java
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++;
```

### CPP

```cpp
class Solution {
public:
  int lengthLongestPath(string input) {
    int i = 0, n = input.size();
    int ans = 0;
    stack<int> stk;
    while (i < n) {
      int ident = 0;
      for (; input[i] == '\t'; ++i) {
        ++ident;
      }
      int cur = 0;
      bool isFile = false;
      for (; i < n && input[i] != '\n'; ++i) {
        ++cur;
        if (input[i] == '.') {
          isFile = true;
        }
      }
      ++i;
```

### Python

```python
class Solution:
    # popd while len ( stk ) > 0 and len ( stk ) > ident : stk . pop () if len ( stk ) > 0 : cur += stk [ - 1 ] + 1 # pushd if not isFile : stk . append ( cur ) continue ans = max ( ans , cur ) return ans
    def lengthLongestPath(self, input: str) -> int: i, n = 0, len(input) ans = 0 stk = [] while i < n: ident = 0 while input[i] == ' \t ': ident += 1 i += 1 cur, isFile = 0, False while i < n and input[i] != ' \n ': cur += 1 if input[i] == '.': isFile = True i += 1 i += 1

```