Longest absolute file path

XXX. Longest Absolute File Path

String

Stack

Problem Statement:

Convert a string representation of a file system (with '\n' and '\t' characters) into absolute paths and find the length of the longest one.

• '\n' separates directories/files
• '\t' indicates depth in directory tree
• Path must end with a file (contains '.')

Implementation:

public int lengthLongestPath(String input) {
    String[] tokens = input.split("\n");
    int result = 0;
    int curLen = 0;
    Stack stack = new Stack<>();

    for (String s : tokens) {
        int level = countLevel(s);                  // Count number of tabs

        // Remove directories deeper than current level
        while (stack.size() > level) 
            curLen -= stack.pop();
        
        // Add current path length (+1 for '/' character)
        int len = s.replaceAll("\t", "").length() + 1;
        curLen += len;

        // Update result if current path ends with a file
        if (s.contains(".")) 
            result = Math.max(result, curLen - 1);  // -1 to remove extra '/'
        
        stack.add(len);                            // Add length to stack
    }
    return result;
}

private int countLevel(String s) {
    String cur = s.replaceAll("\t", "");           // Remove all tabs
    return s.length() - cur.length();              // Count removed tabs
}
                

Complexity:

Time Complexity: O(n), where n is input string length
Space Complexity: O(d), where d is maximum directory depth

Explanation:

• **Stack Usage**:
  • Stack stores length of each directory level
  • Pop when moving to shallower depth
  • Push new lengths for current level
• **Path Length Tracking**:
  • curLen maintains current path length
  • Add +1 for '/' after each directory
  • Remove -1 from final file path (no trailing '/')
• **Level Handling**:
  • Count tabs to determine depth
  • Remove deeper paths when moving up
  • Only update result for complete file paths