[LeetCode] 388. Longest Absolute File Path

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

Use two pointers approach to parse directory / file name.

Use stack to maintain the paths to current files. We need to pop directory from stack is depth of current file is less than the directory on the top of the stack.

Time Complexity = O ( N ).   N = len(input).  As the code only visit each character in the input once.

class Solution:
    def lengthLongestPath(self, input: str) -> int:
        if not input: return 0 
        
        result = 0
        
        # Stack<[fileName, depth]>
        stack = []
            
        left = right  = 0
        depth = 0
        
        while right < len(input):
            if input[right] == '\n' or right == len(input) - 1:
                # pop back to the depth of current file
                while stack and stack[-1][1] >= depth:
                    stack.pop()
                
                # find current file name
                file = input[left:right] if input[right] == '\n' else input[left:right+1]
                stack.append([file, depth])
                
                # calculate the full path to a file
                if '.' in input[left:right]:
                    paths = '/'.join([a for a, _ in stack])
                    result = max(result, len(paths))
                
                # calculate next depth
                right += 1
                left = right
                depth = 0
                
                while right < len(input) and input[right] == '\t':
                    depth += 1
                    right += 1
                
                left = right
            else:
                right += 1
        
        return result