Abstract / Summary

Find the length of the longest absolute path made from directories and files given as strings.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 50% (300k+ submissions).

Typical patterns to solve this problem:

• Depth First Search
• Stack
• String

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation solves the problem of finding the length of the longest absolute path to a file within a virtual file system represented as a single string. The string encodes directories and files using newline characters to separate entries and tab characters to indicate depth. The algorithm walks through each entry once, maintaining a stack-like structure that records the cumulative length of the path up to the current depth. When a file is encountered, the current cumulative length is compared against the best length seen so far.

Core Loop

The heart of the solution is a for loop that iterates over every line obtained by splitting the input on newline characters.

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

During each iteration the algorithm extracts the depth, updates the path length information, and decides whether the line represents a file or a directory.

Depth Management

Depth is derived from the number of leading tab characters. The code trims the tabs list to keep only entries that are relevant for the current depth, effectively discarding deeper levels that are no longer reachable.

tabs = tabs[:line.count("\t") + 1]

By slicing the list to depth + 1 elements, the structure always reflects the path hierarchy up to the current line, ensuring that subsequent length calculations use the correct parent length.

Length Calculation

The length of the current entry without its leading tabs is computed by subtracting the tab count from the total line length. This raw length is then added to the cumulative length of its parent directory, which is stored as the last element of tabs.

length = len(line) - line.count("\t") + tabs[-1]

The resulting length represents the total number of characters from the root to the current entry, not counting the separating slash that will be added for directories.

File Detection

A line is identified as a file if it contains at least one dot character. The presence of a dot triggers an update of the best path length seen so far.

if line.count(".") > 0:
    best = max(best, length)  # file

Because the algorithm already includes the length of the file name, no additional adjustments are required when updating best.

Directory Handling

When the line does not contain a dot, it is treated as a directory. The algorithm records the cumulative length for this directory, adding one to account for the slash that separates it from its children. This value is appended to the tabs list, becoming the new parent length for any deeper entries.

else:
    tabs.append(length + 1)  # directory

The extra +1 ensures that subsequent entries deeper in the hierarchy automatically include the slash in their total length calculation.

Edge Cases Handled

The code gracefully handles an empty input string; the split operation yields a list containing a single empty string, which results in a length of zero and leaves best unchanged. It also correctly processes files located at the root level because a line with zero tabs still produces a valid length and the directory stack is initialized with a zero entry. Multiple consecutive tabs are interpreted as deeper nesting, and the slicing operation guarantees that any stray deeper entries are discarded when the depth decreases. Lines that contain multiple dots are still recognized as files because the condition checks for a count greater than zero, not the position of the dot. Finally, the algorithm tolerates inputs that consist solely of directories without any files; in such cases best remains zero, which correctly reflects the absence of a file path.

Performance Characteristics

The solution processes each line exactly once, performing only constant-time operations per iteration: counting tabs, counting dots, slicing a list, and simple arithmetic. The use of a list to store cumulative lengths provides O(1) access to the parent length, and the slice operation efficiently discards irrelevant deeper levels without needing explicit loops. By avoiding the construction of full path strings and instead working with integer lengths, the algorithm minimizes memory allocations and reduces overhead, leading to a fast and memory-efficient execution path.

Imagine a computer is like a big toy box filled with smaller boxes inside other boxes. Some toys are just plain items, while others are special files that hold things. The code works by looking at a long list of these toy boxes and their names. It starts at the very beginning and walks through every line in the list one by one.

To remember where it is, the code keeps a little shelf of numbers. Every time a line has a tab character, it means that item is tucked inside another box. The code counts these tabs to know how deep it is currently hiding. It calculates how long the path to a toy is by adding up the names of all the boxes it passed through.

Each time it finds a file that has a dot in its name, it measures how long the total path is to reach that file. It compares this length to the longest path it has found before and keeps the biggest number to remember for later. If the line is just a folder that does not have a dot, it adds a new spot on the shelf to help measure the next toys found inside that folder. It keeps going until every line is checked.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

not analyzed yet

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Python		Java						TS
	WalkCCC	C++	Python		Java
	leetcode.ca	C++	Python		Java					Go
	LeetcodeHelp	C++	Python		Java
	MemoryLimitExceeded	C++	Python
	Progiez	C++	Python		Java
github	black-shadows	C++
	charles-wangkai				Java
	everthis			JS
	fartem						Ruby
	Garvit244		Python
	haoel	C++
	JoshCrozier			JS
	linouk23	C++
	lkwq007		Python
	lzl124631x	C++
	qiyuangong		Python
	ruoru					Rust
	suxrobGM							C#
	varunu28				Java
	vli02								C
	wisdompeak	C++
	XiaotaoGuo	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python
LeetcodeHelp	C++, Java, Python
MemoryLimitExceeded	Python, C++
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fartem	Ruby
Garvit244	Python
haoel	C++
JoshCrozier	JavaScript
linouk23	C++
lkwq007	Python
lzl124631x	C++
qiyuangong	Python
ruoru	Rust
suxrobGM	C#
varunu28	Java
vli02	C
wisdompeak	C++
XiaotaoGuo	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality