In this guide, you will get 388. Longest Absolute File Path LeetCode Solution with the best time and space complexity. The solution to Longest Absolute File Path problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
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):
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.
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”.
Constraints:
1 <= input.length <= 104
input may contain lowercase or uppercase English letters, a new line character '\n', a tab character '\t', a dot '.', a space ' ', and digits.
All file and directory names have positive length.
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(n)
388. Longest Absolute File Path LeetCode Solution in C++
struct T {
int depth;
size_t length;
};
class Solution {
public:
int lengthLongestPath(string input) {
size_t ans = 0;
stack<T> stack{{{-1, 0}}}; // placeholder
istringstream iss(input);
for (string token; getline(iss, token, '\n');) {
const int depth = ranges::count(token, '\t');
std::erase(token, '\t');
while (depth <= stack.top().depth)
stack.pop();
if (isFile(token))
ans = max(ans, stack.top().length + token.length());
else // directory + '/'
stack.emplace(depth, stack.top().length + token.length() + 1);
}
return ans;
}
private:
bool isFile(const string& token) {
return token.find('.') != string::npos;
}
}; /* code provided by PROGIEZ */
388. Longest Absolute File Path LeetCode Solution in Java
class T {
public int depth;
public int length;
public T(int depth, int length) {
this.depth = depth;
this.length = length;
}
}
class Solution {
public int lengthLongestPath(String input) {
int ans = 0;
Deque<T> stack = new ArrayDeque<>();
stack.push(new T(-1, 0));
for (String token : input.split("\n")) {
final int depth = getDepth(token);
token = token.replace("\t", "");
while (depth <= stack.peek().depth)
stack.pop();
if (token.contains(".")) // `token` is file.
ans = Math.max(ans, stack.peek().length + token.length());
else // directory + '/'
stack.push(new T(depth, stack.peek().length + token.length() + 1));
}
return ans;
}
private int getDepth(final String token) {
return (int) token.chars().filter(c -> c == '\t').count();
}
} // code provided by PROGIEZ
388. Longest Absolute File Path LeetCode Solution in Python
class Solution:
def lengthLongestPath(self, input: str) -> int:
ans = 0
stack = [(-1, 0)] # placeholder
for token in input.split('\n'):
depth = token.count('\t')
token = token.replace('\t', '')
while depth <= stack[-1][0]:
stack.pop()
if '.' in token: # `token` is file.
ans = max(ans, stack[-1][1] + len(token))
else: # directory + '/'
stack.append((depth, stack[-1][1] + len(token) + 1))
return ans # code by PROGIEZ
