Longest Absolute File Path
Problem
Given a string representing the file system encoded with '\n' (newline) and '\t' (tab) to indicate depth, return the length of the longest absolute path to a file (including '/' separators). If no file exists, return 0.
"dir\n\tsub1\n\t\tfile1.ext\n\tsub2\n\t\tfile2"18def length_longest_path(s):
best = 0
lengths = {0: 0}
for line in s.split('\n'):
name = line.lstrip('\t')
depth = len(line) - len(name)
if '.' in name:
best = max(best, lengths[depth] + len(name))
else:
lengths[depth + 1] = lengths[depth] + len(name) + 1
return bestfunction lengthLongestPath(s) {
let best = 0;
const lengths = { 0: 0 };
for (const line of s.split('\n')) {
const name = line.replace(/^\t+/, '');
const depth = line.length - name.length;
if (name.includes('.')) {
best = Math.max(best, lengths[depth] + name.length);
} else {
lengths[depth + 1] = lengths[depth] + name.length + 1;
}
}
return best;
}class Solution {
public int lengthLongestPath(String input) {
int best = 0;
Map<Integer, Integer> lengths = new HashMap<>();
lengths.put(0, 0);
for (String line : input.split("\n")) {
String name = line.replaceAll("^\\t+", "");
int depth = line.length() - name.length();
if (name.contains(".")) best = Math.max(best, lengths.get(depth) + name.length());
else lengths.put(depth + 1, lengths.get(depth) + name.length() + 1);
}
return best;
}
}int lengthLongestPath(string s) {
int best = 0;
unordered_map<int, int> lengths; lengths[0] = 0;
stringstream ss(s); string line;
while (getline(ss, line, '\n')) {
int depth = 0; while (depth < (int)line.size() && line[depth] == '\t') depth++;
string name = line.substr(depth);
if (name.find('.') != string::npos) best = max(best, lengths[depth] + (int)name.size());
else lengths[depth + 1] = lengths[depth] + (int)name.size() + 1;
}
return best;
}Explanation
The input encodes a tree with tabs for depth and newlines between entries. Instead of building the actual tree, we just track, for each depth, the total path length of the parent so far — a depth-indexed running total that behaves like a stack.
We split on \n and process each line. The number of leading \t tabs is the depth, and the rest is the name. We keep lengths, where lengths[depth] is the length of the full path leading up to (but not including) an item at that depth.
If a name contains a '.' it is a file, so a complete path length is lengths[depth] + len(name), and we update best. Otherwise it is a directory, and we record lengths[depth + 1] = lengths[depth] + len(name) + 1, where the +1 accounts for the '/' separator.
Example: dir/sub1/file1.ext from the sample. dir sets depth-1 to 4, sub1 sets depth-2 to 9, then file1.ext (length 9) gives 9 + 9 = 18, the longest.
Each line is read once and updates a small map, so the algorithm is linear and uses space proportional to the maximum depth.