# LeetCode 388: Longest Absolute File Path

## Problem Restatement

We are given a string `input` that represents a file system.

Each file or directory appears on its own line.

A newline character means a new entry:

```python
"\n"
```

A tab character at the start of a line tells us the depth:

```python
"\t"
```

A file is identified by having a dot `.` in its name.

We need to return the length of the longest absolute path to any file. If there is no file, return `0`.

For example, this path:

```text
dir/subdir2/subsubdir2/file2.ext
```

has length `32`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | A serialized file system string |
| Output | Length of the longest absolute path to a file |
| Directory depth | Number of leading tab characters |
| File marker | A name containing `.` |
| No files | Return `0` |

Example function shape:

```python
def lengthLongestPath(input: str) -> int:
    ...
```

## Examples

Example 1:

```python
input = "dir\n\tsubdir1\n\tsubdir2\n\t\tfile.ext"
```

This represents:

```text
dir
    subdir1
    subdir2
        file.ext
```

The file path is:

```text
dir/subdir2/file.ext
```

Its length is:

```python
len("dir/subdir2/file.ext") == 20
```

So the answer is:

```python
20
```

Example 2:

```python
input = "dir\n\tsubdir1\n\t\tfile1.ext\n\t\tsubsubdir1\n\tsubdir2\n\t\tsubsubdir2\n\t\t\tfile2.ext"
```

The files are:

```text
dir/subdir1/file1.ext
dir/subdir2/subsubdir2/file2.ext
```

Their lengths are:

```python
len("dir/subdir1/file1.ext") == 21
len("dir/subdir2/subsubdir2/file2.ext") == 32
```

So the answer is:

```python
32
```

Example 3:

```python
input = "a"
```

There is only a directory and no file.

So the answer is:

```python
0
```

## First Thought: Build the Whole Tree

One direct approach is to parse the string into an actual tree.

Each directory becomes a tree node.

Each file becomes a leaf.

Then we can traverse the tree and compute every file path length.

This works, but it is more structure than we need.

We do not need the tree itself. We only need the current path length at each depth.

## Key Insight

When reading a line, its number of leading tabs gives its depth.

For example:

```text
dir                  depth 0
    subdir2          depth 1
        file.ext     depth 2
```

If we know the full path length up to depth `1`, then we can compute the file path at depth `2`.

For:

```text
dir/subdir2/file.ext
```

we need:

```python
len("dir/subdir2/") + len("file.ext")
```

So we keep a table:

```python
path_len[depth]
```

where `path_len[d]` means the total length of the path prefix up to depth `d`, including the trailing slash.

For example:

```python
path_len[0] = len("dir/")
path_len[1] = len("dir/subdir2/")
```

Then when we see a file at depth `2`, its full length is:

```python
path_len[1] + len("file.ext")
```

## Algorithm

Split the input into lines:

```python
lines = input.split("\n")
```

Create a map for prefix lengths:

```python
path_len = {0: 0}
```

Here, `path_len[0] = 0` means there is no prefix before a root-level entry.

For each line:

1. Count the number of leading tabs. This is `depth`.
2. Remove those tabs to get the name.
3. If the name contains `.`, it is a file.
   - Its full path length is `path_len[depth] + len(name)`.
   - Update the answer.
4. Otherwise, it is a directory.
   - Store the prefix length for its children:
   ```python id="o6qzbj"
   path_len[depth + 1] = path_len[depth] + len(name) + 1
   ```
   The `+ 1` is for the slash `/`.

## Correctness

The value `path_len[d]` stores the length of the absolute path prefix before an entry at depth `d`.

For depth `0`, this prefix is empty, so `path_len[0] = 0`.

When the parser reads a directory at depth `d`, every child of that directory appears at depth `d + 1`. The child prefix consists of the parent prefix, the directory name, and one slash. Therefore:

```python
path_len[d + 1] = path_len[d] + len(name) + 1
```

is correct.

When the parser reads a file at depth `d`, its absolute path consists of the prefix before depth `d` plus the file name. Therefore:

```python
path_len[d] + len(name)
```

is exactly the file path length.

The algorithm evaluates every file line and takes the maximum of these exact lengths. If no file appears, the maximum remains `0`.

Therefore the returned value is the length of the longest absolute path to a file.

## Complexity

Let `n = len(input)`.

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | Each character is processed while splitting and scanning lines |
| Space | `O(d)` | `path_len` stores one value per depth |

`d` is the maximum directory nesting depth.

## Implementation

```python
class Solution:
    def lengthLongestPath(self, input: str) -> int:
        path_len = {0: 0}
        best = 0

        for line in input.split("\n"):
            depth = line.count("\t")
            name = line.lstrip("\t")

            if "." in name:
                best = max(best, path_len[depth] + len(name))
            else:
                path_len[depth + 1] = path_len[depth] + len(name) + 1

        return best
```

## Code Explanation

We store prefix lengths by depth:

```python
path_len = {0: 0}
```

The root level has no parent prefix.

The answer starts at `0`:

```python
best = 0
```

We process each file-system entry line by line:

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

The depth is the number of leading tabs:

```python
depth = line.count("\t")
```

In this problem, tabs appear only as indentation at the start of a line, so this gives the depth.

Remove the tabs to get the actual file or directory name:

```python
name = line.lstrip("\t")
```

If the name contains a dot, it is a file:

```python
if "." in name:
```

Then compute the absolute path length:

```python
path_len[depth] + len(name)
```

If the name is a directory, compute the prefix length for its children:

```python
path_len[depth + 1] = path_len[depth] + len(name) + 1
```

The `+ 1` accounts for the slash between path components.

## Testing

```python
def test_solution():
    s = Solution()

    assert s.lengthLongestPath(
        "dir\n\tsubdir1\n\tsubdir2\n\t\tfile.ext"
    ) == 20

    assert s.lengthLongestPath(
        "dir\n\tsubdir1\n\t\tfile1.ext\n\t\tsubsubdir1\n"
        "\tsubdir2\n\t\tsubsubdir2\n\t\t\tfile2.ext"
    ) == 32

    assert s.lengthLongestPath("a") == 0

    assert s.lengthLongestPath("file.txt") == 8

    assert s.lengthLongestPath(
        "a\n\tb\n\t\tc.txt\n\td.txt"
    ) == 9

    assert s.lengthLongestPath(
        "dir\n\tfile.txt\n\tlongdirname\n\t\tlongfile.txt"
    ) == len("dir/longdirname/longfile.txt")

    print("all tests passed")

test_solution()
```

Test meaning:

| Test | Why |
|---|---|
| Simple nested file | Basic directory and file path |
| Official-style nested example | Checks longest among multiple files |
| `"a"` | No file, return `0` |
| `"file.txt"` | File at root level |
| Mixed depths | Checks sibling file after nested directory |
| Longer nested path | Confirms maximum update across branches |