algoadvance

Leetcode 388. Longest Absolute File Path

Problem Statement

You are given a string representation of a file system in which different levels of directories and files are separated by newline (\n) characters and where each level is indicated by a number of tab (\t) characters.

For example, a string "dir\n\tsubdir1\n\tsubdir2\n\t\tfile.ext" represents a file system such that:

dir
    subdir1
    subdir2
        file.ext

Here, the longest absolute path to a file is "dir/subdir2/file.ext", and its length is 20 (note that the forward slashes are not counted as separators between directories and files).

Write a program that finds the length of the longest absolute path to a file in the given string representation of the file system. If there is no file in the system, return 0.

Clarifying Questions

  1. What constitutes a file vs. a directory?
    • A filename will contain a period (.) character which implies it is a file; otherwise, it is a directory.
  2. What are the constraints on the input?
    • The input string length will not exceed 10^4.
    • The input string can contain any printable ASCII characters.
  3. Can the directories and files have the same name?
    • Yes, it’s possible for directories and files to have the same name as per the problem constraints.

Strategy

  1. Parse the Input:
    • Use the newline character (\n) to split the string into different components representing files and directories.
  2. Depth Handling:
    • Use the tab character (\t) to determine the depth level of each component. The number of \t characters directly relates to the depth of the file or directory.
  3. Track Paths:
    • Use a stack to keep track of the current path length at each directory level.
  4. Update Longest Path:
    • When encountering a file, update the longest path length if the current file path length is greater than the previous maximum.

Code

#include <iostream>
#include <sstream>
#include <vector>
#include <stack>
#include <algorithm>

int lengthLongestPath(const std::string &input) {
    std::istringstream ss(input);
    std::string line;
    std::stack<int> pathStack;
    int maxLength = 0;
    
    while (std::getline(ss, line)) {
        size_t numTabs = line.find_first_not_of("\t");
        int level = numTabs;
        std::string name = line.substr(numTabs);
        
        while (pathStack.size() > level) {
            pathStack.pop();
        }

        int currLength = name.size() + (pathStack.empty() ? 0 : pathStack.top() + 1); // +1 for '/' between dirs/files
        if (name.find('.') != std::string::npos) {
            maxLength = std::max(maxLength, currLength);
        } else {
            pathStack.push(currLength);
        }
    }

    return maxLength;
}

int main() {
    std::string input = "dir\n\tsubdir1\n\tsubdir2\n\t\tfile.ext";
    std::cout << "The longest path length is: " << lengthLongestPath(input) << std::endl;
    return 0;
}

Time Complexity

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI