Last updated on January 9th, 2025 at 03:36 am
Here, we see the Longest Absolute File Path LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.
List of all LeetCode Solution
Topics
String
Companies
Level of Question
Medium
Longest Absolute File Path LeetCode Solution
Table of Contents
1. Problem Statement
Suppose we have a file system that stores both files and directories. An example of one system is represented in the following picture:
Here, we have dir as the only directory in the root. dir contains two subdirectories, subdir1 and subdir2. subdir1 contains a file file1.ext and subdirectory subsubdir1. subdir2 contains a subdirectory subsubdir2, which contains a file file2.ext.
In text form, it looks like this (with ⟶ representing the tab character):dir ⟶ subdir1 ⟶ ⟶ file1.ext ⟶ ⟶ subsubdir1 ⟶ subdir2 ⟶ ⟶ subsubdir2 ⟶ ⟶ ⟶ file2.ext
If we were to write this representation in code, it will look like this: “dir\n\tsubdir1\n\t\tfile1.ext\n\t\tsubsubdir1\n\tsubdir2\n\t\tsubsubdir2\n\t\t\tfile2.ext”. Note that the ‘\n’ and ‘\t’ are the new-line and tab characters.
Every file and directory has a unique absolute path in the file system, which is the order of directories that must be opened to reach the file/directory itself, all concatenated by ‘/’s. Using the above example, the absolute path to file2.ext is “dir/subdir2/subsubdir2/file2.ext”. Each directory name consists of letters, digits, and/or spaces. Each file name is of the form name.extension, where name and extension consist of letters, digits, and/or spaces.
Given a string input representing the file system in the explained format, return the length of the longest absolute path to a file in the abstracted file system. If there is no file in the system, return 0.
Note that the testcases are generated such that the file system is valid and no file or directory name has length 0.
Example 1:
Input: input = “dir\n\tsubdir1\n\tsubdir2\n\t\tfile.ext”
Output: 20
Explanation: We have only one file, and the absolute path is “dir/subdir2/file.ext” of length 20.
Example 2:
Input: input = “dir\n\tsubdir1\n\t\tfile1.ext\n\t\tsubsubdir1\n\tsubdir2\n\t\tsubsubdir2\n\t\t\tfile2.ext”
Output: 32
Explanation: We have two files: “dir/subdir1/file1.ext” of length 21 “dir/subdir2/subsubdir2/file2.ext” of length 32. We return 32 since it is the longest absolute path to a file.
Example 3:
Input: input = “a”
Output: 0
Explanation: We do not have any files, just a single directory named “a”.
2. Coding Pattern Used in Solution
The coding pattern used in this problem is “Path Parsing”. The code processes a string representation of a file system, calculates the depth of each directory or file, and keeps track of the cumulative path lengths to determine the longest absolute path to a file.
3. Code Implementation in Different Languages
3.1 Longest Absolute File Path C++
class Solution {
public:
int lengthLongestPath(string input) {
deque<int> dq;
int len = 0, res = 0, level = 0;
bool file = false;
for(char c: input){
if(c == '\n'){
dq.push_back(len);
level = len = file = 0;
}
else if(c == '\t') ++level;
else if(c == '.') ++len, file = true;
else{
++len;
if(file) res = max(res, len + accumulate(dq.begin(), dq.end(), 0) + level);
while(level < dq.size()){
dq.pop_back();
}
}
}
return res;
}
};
3.2 Longest Absolute File Path Java
class Solution {
public int lengthLongestPath(String input) {
String[] lines = input.split("\n");
int maxLength = 0;
HashMap<Integer, Integer> pathLengths = new HashMap<>();
for (String line : lines) {
String name = line.replaceAll("\t", "");
int depth = line.length() - name.length();
boolean isFile = name.contains(".");
if (isFile) {
maxLength = Math.max(maxLength, pathLengths.get(depth) + name.length());
} else {
pathLengths.put(depth + 1, pathLengths.getOrDefault(depth, 0) + name.length() + 1);
}
}
return maxLength;
}
}
3.3 Longest Absolute File Path JavaScript
var lengthLongestPath = function(input) {
let dir = input.split('\n');
let max = 0;
let length = [];
let depth= 0;
for (let i=0;i<dir.length;i++) {
depth = dir[i].lastIndexOf('\t')+1;
if (dir[i].includes('.')) {
let fileLength = dir[i].length-depth;
max = Math.max((length[depth-1]+1||0) + fileLength , max);
} else {
length[depth] = dir[i].length - depth + (length[depth-1]+1||0);
}
}
return max;
};
3.4 Longest Absolute File Path Python
class Solution(object):
def lengthLongestPath(self, input):
lines = input.split('\n')
max_length = 0
path_lengths = {0: 0}
for line in lines:
name = line.lstrip('\t')
depth = len(line) - len(name)
is_file = '.' in name
if is_file:
max_length = max(max_length, path_lengths[depth] + len(name))
else:
path_lengths[depth + 1] = path_lengths[depth] + len(name) + 1
return max_length
4. Time and Space Complexity
| Time Complexity | Space Complexity | |
| C++ | O(n) | O(d) |
| Java | O(n) | O(d) |
| JavaScript | O(n) | O(d) |
| Python | O(n) | O(d) |
here,
n: Total number of characters in the input string.
d: Maximum depth of the file system hierarchy.
- The problem is solved using a hierarchical parsing approach, where the depth of each line is calculated and used to manage cumulative path lengths.
- The code is efficient, as it processes the input in a single pass and uses minimal additional space proportional to the depth of the file system.