Longest Absolute File Path - Practice Coding Problems

Longest Absolute File Path - Problem

Suppose we have a file system that stores both files and directories. Given a string input representing the file system in a specific format, return the length of the longest absolute path to a file in the abstracted file system.

The input string uses \n (newline) to separate different files/directories, and \t (tab) characters to represent the depth level in the directory hierarchy.

Each file name is of the form name.extension, while directory names consist of letters, digits, and/or spaces without extensions.

For example:

"dir\n\tsubdir1\n\t\tfile1.ext\n\t\tsubsubdir1\n\tsubdir2\n\t\tsubsubdir2\n\t\t\tfile2.ext"

represents the directory structure where file2.ext has the absolute path "dir/subdir2/subsubdir2/file2.ext" with length 32.

If there is no file in the system, return 0.

Input & Output

Example 1 — Basic Directory Structure

$ Input: input = "dir\n\tsubdir1\n\t\tfile1.ext\n\t\tsubsubdir1\n\tsubdir2\n\t\tsubsubdir2\n\t\t\tfile2.ext"

› Output: 32

💡 Note: The longest path is "dir/subdir2/subsubdir2/file2.ext" with length 32. This beats "dir/subdir1/file1.ext" which has length 20.

Example 2 — Single File

$ Input: input = "file1.txt"

› Output: 9

💡 Note: Only one file exists at root level with name "file1.txt", so the length is 9.

Example 3 — No Files

$ Input: input = "dir1\n\tdir2\n\t\tdir3"

› Output: 0

💡 Note: All entries are directories (no extensions), so no files exist. Return 0.

Constraints

1 ≤ input.length ≤ 10⁴
input contains only valid directory/file names
File names contain exactly one '.' character
No empty directory or file names

Visualization

Tap to expand

Understanding the Visualization

Input

Parse directory structure with tab indentation

Process

Track path lengths using stack based on nesting depth

Output

Return length of longest absolute file path

Key Takeaway

🎯 Key Insight: Use a stack to track directory path lengths at each depth level - only calculate full paths when you encounter files

Asked in

G Google 35 A Amazon 28 M Microsoft 22 F Facebook 18

The key insight is to use a stack to efficiently track directory path lengths at each nesting level. Best approach is the stack-based solution which processes input in a single pass. Time: O(n), Space: O(d) where d is maximum directory depth.

Common Approaches

Approach	Time	Space	Notes
✓ Generate All Paths	O(n²)	O(n²)	Build all possible directory paths and find longest file path
Stack-Based Path Tracking	O(n)	O(d)	Use stack to track current directory path and lengths efficiently

Generate All Paths — Algorithm Steps

Parse input into tree structure
Recursively generate all paths
Find longest path to a file

Visualization

Tap to expand

Step-by-Step Walkthrough

Parse Structure

Split input by newlines and identify depth levels

Build All Paths

Recursively construct every possible path string

Find Maximum

Track longest path that ends with a file

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int buildPaths(char lines[][256], int numLines, int startIdx, char* currentPath, int currentDepth) {
    int maxLen = 0;
    int i = startIdx;
    
    while (i < numLines) {
        char* line = lines[i];
        int depth = 0;
        while (depth < strlen(line) && line[depth] == '\t') {
            depth++;
        }
        
        if (depth < currentDepth) {
            break;
        } else if (depth == currentDepth) {
            char* name = line + depth;
            char newPath[1024];
            if (strlen(currentPath) == 0) {
                strcpy(newPath, name);
            } else {
                sprintf(newPath, "%s/%s", currentPath, name);
            }
            
            if (strstr(name, ".")) {
                int len = strlen(newPath);
                if (len > maxLen) maxLen = len;
            } else {
                int subLen = buildPaths(lines, numLines, i + 1, newPath, depth + 1);
                if (subLen > maxLen) maxLen = subLen;
            }
        }
        i++;
    }
    
    return maxLen;
}

int solution(char* input) {
    if (strlen(input) == 0) return 0;
    
    char lines[100][256];
    int numLines = 0;
    
    char* token = strtok(input, "\n");
    while (token != NULL && numLines < 100) {
        strcpy(lines[numLines], token);
        numLines++;
        token = strtok(NULL, "\n");
    }
    
    return buildPaths(lines, numLines, 0, "", 0);
}

int main() {
    char input[10000];
    fgets(input, sizeof(input), stdin);
    input[strcspn(input, "\n")] = 0;
    
    // Remove quotes if present
    int len = strlen(input);
    if (len >= 2 && input[0] == '"' && input[len-1] == '"') {
        memmove(input, input + 1, len - 1);
        input[len - 2] = '\0';
    }
    
    printf("%d\n", solution(input));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

Building tree and generating all paths can visit each node multiple times

⚠ Quadratic Growth

Space Complexity

O(n²)

Stores complete tree structure and all generated path strings

⚠ Quadratic Space

67.0K Views

Medium Frequency

~25 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Generate All Paths — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler