SAMSUNG 49-Inch Odyssey G9

Because earth is not flat

Description

Given a string input that represents a file system, where each folder or file is separated by newline characters (\n) and the level of each file or folder is determined by the number of tab characters (\t), return the length of the longest path to a file in the file system.

The path must be absolute, meaning it starts from the root directory and ends at a file. If there is no file in the system, return 0.

Intuition

The problem can be interpreted as a tree structure where folders are nodes and files are leaves. Each file or folder is indented using tabs, signifying its level in the directory hierarchy. The challenge is to calculate the longest path to a file while accounting for directory structure.

To solve this, we can utilize a stack that helps track the length of the current directory path. By traversing the input string line by line, we update the stack as we move deeper into or back out of directories.

Approach

1. Initialization: Use a stack where the top of the stack represents the cumulative length of the path at the current directory level.
2. Process each line: Split the input by newlines. For each part (directory or file):
   • Determine its depth by counting the number of tabs (\t).
   • Adjust the stack to reflect the current depth by popping elements from it until the stack matches the current level.
   • Calculate the length of the path for the current part and push it onto the stack.
   • If the part is a file (contains a .), update the maximum path length.
3. Edge case: If no file is found, return 0.

Complexity

Time Complexity:

O(n), where n is the length of the input string. We process each character of the input exactly once, splitting it into parts and updating the stack as needed.

Space Complexity:

O(d), where d is the depth of the deepest directory in the input. The stack grows based on the depth of the directory structure.

Code

C++

class Solution {
public:
    int lengthLongestPath(std::string input) {
        std::vector<int> stack = {0};  // Initialize with 0 to avoid empty stack issues
        int maxLen = 0;
        std::stringstream ss(input);
        std::string part;

        while (std::getline(ss, part, '\n')) {
            int level = part.find_last_of('\t') + 1;  // Level is determined by the number of tabs
            while (level + 1 < stack.size()) {
                stack.pop_back();  // Pop until the stack matches the current level
            }
            int length = stack.back() + part.length() - level + 1;  // Length includes '/'
            stack.push_back(length);

            if (part.find('.') != std::string::npos) {
                maxLen = std::max(maxLen, length - 1);  // Update max length if part contains '.'
            }
        }
        return maxLen;
    }
};

Python

class Solution:
    def lengthLongestPath(self, input: str) -> int:
        stack = [0]  # Initialize stack with 0 to avoid empty stack issues
        max_len = 0
        for part in input.split("\n"):
            level = part.rfind("\t") + 1  # Level is determined by the number of tabs
            while level + 1 < len(stack):
                stack.pop()  # Pop until the stack matches the current level
            length = stack[-1] + len(part) - level + 1  # Length includes '/'
            stack.append(length)

            if '.' in part:
                max_len = max(max_len, length - 1)  # Update max length if part contains '.'

        return max_len

Java

class Solution {
    public int lengthLongestPath(String input) {
        Stack<Integer> stack = new Stack<>();
        stack.push(0);  // Initialize stack with 0 to avoid empty stack issues
        int maxLen = 0;
        String[] parts = input.split("\n");

        for (String part : parts) {
            int level = part.lastIndexOf("\t") + 1;  // Level is determined by the number of tabs
            while (level + 1 < stack.size()) {
                stack.pop();  // Pop until the stack matches the current level
            }
            int length = stack.peek() + part.length() - level + 1;  // Length includes '/'
            stack.push(length);

            if (part.contains(".")) {
                maxLen = Math.max(maxLen, length - 1);  // Update max length if part contains '.'
            }
        }
        return maxLen;
    }
}

JavaScript

var lengthLongestPath = function (input) {
    let stack = [0];
    let maxLen = 0;
    input.split("\n").forEach(part => {
        let level = part.lastIndexOf("\t") + 1;
        while (level + 1 < stack.length) {
            stack.pop();
        }
        let length = stack[stack.length - 1] + part.length - level + 1;
        stack.push(length);
        if (part.includes(".")) {
            maxLen = Math.max(maxLen, length - 1);
        }
    })
    return maxLen;
};