Problem statement

https://leetcode.com/problems/longest-absolute-file-path/

Solution 1

We need to traverse our string and keep stack with current file or directory. What we can do first is to preprocess our data, split it using \n (actually split by lines). When we did it, find number of \t in the beginning of each line, it will be our depth level. Now, we put elements to stack if we go deeper and remove elements from stack, when we have smaller level. Compute on each iteration current length so-far and update maximum when we meet file, that is it has dot in its name.

Complexity

Time complexity is O(n), because we process each line at most 2 times: when we put it into stack and when we remove it. Space complexity is also potentially O(n).

Code

class Solution:
    def lengthLongestPath(self, inp):
        ans, stack = 0, [(-1, 0)]
        for line in inp.split('\n'):
            depth = line.count('\t')
            
            while stack[-1][0] >= depth: stack.pop()
            if "." in line: 
                ans = max(ans, stack[-1][1] + len(line) - depth)
            else:
                stack.append((depth, stack[-1][1] + len(line) - depth + 1))
        return ans

Solution 2

We can keep dictionary d, where we keep for each level the last directory we met in this level. On each iteration we check depth and update d[dpeth]. Then we check if it is file we have now and if it is file, we update ans.

Complexity

It is also O(n) for time and space.

Code

class Solution:
    def lengthLongestPath(self, inp):
        ans, d = 0, {-1: 0}
        for line in inp.split('\n'):
            depth = line.count('\t')
            d[depth] = d[depth - 1] + len(line) - depth + 1
            if line.count('.'):
                ans = max(ans, d[depth] - 1)
                
        return ans