Practice/Datadog/Leetcode 388. Longest Absolute File Path

Leetcode 388. Longest Absolute File Path

CodingMust

Problem

You are given a text representation of a file system structure where directories and files are organized hierarchically. The string uses newline characters (\n) to separate entries and tab characters (\t) to indicate nesting depth. Each tab represents one level deeper in the directory tree.

Your task is to find the length of the longest absolute path to any file in this representation. The absolute path length includes the names of all directories in the path plus the file name, with forward slashes (/) separating each component. A file is identified by having an extension (contains a period).

If no files exist in the structure, return 0.

Requirements

1. Parse the input string to identify directories and files at different nesting levels
2. Calculate the absolute path length for each file found
3. Return the length of the longest absolute path
4. Only count paths that lead to files (entries containing a period)
5. Include slashes in the path length calculation (but not at the beginning)

Constraints

• 1 ≤ input.length ≤ 10⁴
• The input string contains only lowercase letters, digits, periods, newlines, and tabs
• All directory and file names have at least one character
• The input represents a valid file system structure
• Time complexity should be O(n) where n is the length of the input string
• Space complexity should be O(d) where d is the maximum depth of nesting

Examples

Example 1:

Input: "dir\n\tsubdir1\n\tsubdir2\n\t\tfile.ext" Output: 20 Explanation: We have the structure: dir subdir1 subdir2 file.ext The longest path is "dir/subdir2/file.ext" which has length 3+1+7+1+8 = 20

Example 2:

Input: "dir\n\tsubdir1\n\t\tfile1.ext\n\t\tsubsubdir1\n\tsubdir2\n\t\tsubsubdir2\n\t\t\tfile2.ext" Output: 32 Explanation: We have the structure: dir subdir1 file1.ext subsubdir1 subdir2 subsubdir2 file2.ext The longest paths are "dir/subdir1/file1.ext" (length 20) and "dir/subdir2/subsubdir2/file2.ext" (length 32). The answer is 32 since it's the longest.

Example 3:

Input: "dir\n\tsubdir1\n\t\tsubsubdir1" Output: 0 Explanation: No files exist (no entry contains a period), so return 0