O(n) time O(n) space stack solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class Solution {
    public int lengthLongestPath(String input) {
        String[] lines = input.split("\n");
        Stack<Integer> path = new Stack<>();
        path.push(0);
        int max = 0;
        
        for (String line : lines) {
            int tabIndex = line.lastIndexOf("\t") + 1;
            while (path.size() - 1 > tabIndex) {
                path.pop();
            }
            int length = path.peek() + 1 + line.length() - tabIndex;
            path.push(length);
            if (line.indexOf(".") != -1)
                max = Math.max(max, length - 1);
        }
        
        return max;
    }
}

O(n) time O(n) DP solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Solution {
    public int lengthLongestPath(String input) {
        String[] lines = input.split("\n");
        int[] length = new int[lines.length + 1];
        int max = 0;
        
        for (String line : lines) {
            int depth = line.lastIndexOf("\t") + 1;
            length[depth + 1] = length[depth] + 1 + line.length() - depth;
            if (line.indexOf(".") != -1) {
                max = Math.max(max, length[depth + 1] - 1);
            }
        }
        return max;
    }
}