Longest Absolute File Path

Moderate
0/80
Average time to solve is 10m
profile
Contributed by
5 upvotes
Asked in companies
UberNagarro Software

Problem statement

You are given a string, ‘S’, representing the path in the file system. Your task is to find the longest absolute file path.

In a file system, a directory doesn’t have an extension, whereas a file does have an extension. Eg: dir is a directory and file.txt is a file.

Example:

For the below file system, the string S will be:
S = “dir\n\tsubdir1\n\t\tfile1.txt\n\t\tfile2.txt\n\tfile.txt”

file path

The above string will actually be represented as:

dir
    subdir1
        file1.txt
        file2.txt
    file.txt

Where character \n is the next line, and \t is the tab character i.e in the actual string instead of \t we will have a tab.

Every file has a unique absolute path.

Example:

file2.txt has an absolute path “dir/subdir1/file2.txt” and file.txt has path “dir/file.txt”.
The absolute file path length is the length of this string.
So absolute path length for file file2.txt will be the length of string “dir/subdir1/file2.txt” which is 21.

You need to print the longest of all such possible absolute file path lengths.

Note: 
If there is no file in the system, return 0.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of the input contains the string ‘S’.

Note:

The first line of each input contains an integer that denotes the number of lines that will be given but this integer is not passed to the function because one of the aim of this question is to read input until EOF(End of the file).
Output Format: 
The only line of output prints a single integer denoting the longest absolute file path.
Constraints: 
0 <= |S| <= 5 * 10^3

Where |S| denotes the length of string S

Time limit: 1 sec
Sample Input 1:
5
dir
-subdir1
--file1.txt
--file2.txt
-file.txt
Sample Output 1:
21
Explanation for Sample Input 1:
There are three file paths possible
“dir/subdir1/file1.txt” of length 21
“dir/subdir1/file2.txt” of length 21
“dir/file.txt” of length 12

Therefore longest file path is of length 21.
Sample Input 2:
4 
dir
-subdir1
--subsubdir2
-subdir
Sample Output 2:
0
Hint

Try to store the length of the previous folder in a data structure like stack.

Approaches (1)
stack

The key idea in this approach is to traverse the string line by line and count the number of tabs to get the depth of the current directory/file while maintaining a stack that stores all previous directories needed to reach the current directory/file.

Algorithm:

  • Initially 'RES'=0, 'LEN'=0, which denotes the final result and the current length of the path respectively.
  • Traverse through the string ‘S’ line by line.
  • Count the current depth corresponding to the root directory by counting the number of tabs,i.e. Count the number of consecutive positions with S[i]==’\t’.
  • If the current depth is less than or equal to stack size then pop the stack until stack size is less than the current depth, this will make sure we have the right directory order to reach the current directory/file, when we pop from the stack we reduce the ‘LEN’ variable also.
  • The stack we have will store the length of the directory names which will help us in building up our answer because, in the end, all we need is the sum of lengths of the directory names.
  • If currently, we have a directory we just push its name length in the stack and add it into 'LEN' variable.
  • If ‘.’ is found during the process, it means currently we don’t have a directory but a file. So after adding it to the len we update our final answer.
Time Complexity

O(|S|),  where ‘|S|’ is the length of the string.

 

We are only iterating in the string so, the time complexity is O(|S|)

Space Complexity

O(1)

 

We are only using the original string and not creating a new string.

Code Solution
(100% EXP penalty)
Longest Absolute File Path
Full screen
Console