Longest Absolute File Path Problem


Description

LeetCode Problem 388.

Suppose we have a file system that stores both files and directories.

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):

1
2
3
4
5
6
7
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.

Example 1:

1
2
3
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:

1
2
3
4
5
6
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:

1
2
3
Input: input = "a"
Output: 0
Explanation: We do not have any files, just a single directory named "a".

Example 4:

1
2
3
4
Input: input = "file1.txt\nfile2.txt\nlongfile.txt"
Output: 12
Explanation: There are 3 files at the root directory.
Since the absolute path for anything at the root directory is just the name itself, the answer is "longfile.txt" with length 12.

Constraints:

  • 1 <= input.length <= 10^4
  • input may contain lowercase or uppercase English letters, a new line character ‘\n’, a tab character ‘\t’, a dot ‘.’, a space ‘ ‘, and digits.


Sample C++ Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int lengthLongestPath(string input) {
    	// Main idea is using hashmap to store the path length for each depth. 
    	// The depth is the number of "\t". For each filename, 
    	// calculate the path length by the current depth.
        istringstream ss(input);
        string cur;
        int result = 0;
        unordered_map<int, int> pathLen;
        while (getline(ss, cur, '\n')) {
            auto depth = cur.find_last_of("\t");
            string name = (depth == string::npos) ? cur : cur.substr(depth + 1);
            if (cur.find(".") != string::npos) {
                result = max(result, pathLen[depth - 1] + (int)name.size());
            }
            else {
                pathLen[depth] = pathLen[depth - 1] + name.size() + 1;
            }
        }
        return result;
    }
};




Related Posts

Find Duplicate Subtrees Problem

LeetCode 652. Given the rootof a binary tree, return all...

Delete And Earn Problem

LeetCode 740. You are given an integer array nums. You...

Degree Of An Array Problem

LeetCode 697. Given a non-empty array of non-negative integers nums,...

Custom Sort String Problem

LeetCode 791. You are given two strings order and s....

Basic Calculator IV Problem

LeetCode 770. Given an expression such as expression = “e...

Sort Characters By Frequency Problem

LeetCode 451. Given a string s, sort it in decreasing...